Count Distinct Numbers on Board

Easy
693.

Count Distinct Numbers on Board

Count Distinct Numbers on Board is an easy coding problem on math, simulation and number theory, asked in Amazon, TCS and Zoho interviews.

You write n on a board. Every day, for each number x already on the board, you add every y in [1, n] such that x % y == 1. Numbers never repeat on the board.

Return how many distinct numbers the board holds after 10^9 days.

Example 1

Input
n = 5
Output
4
Explanation
5 % 4 = 1 adds 4; then 4 % 3 = 1 adds 3; then 3 % 2 = 1 adds 2. The board ends as {2,3,4,5}.

Example 2

Input
n = 3
Output
2
Explanation
3 % 2 = 1 adds 2, and 2 adds nothing new.

Example 3

Input
n = 1
Output
1
Explanation
1 % y == 1 has no solution in range, so only 1 stays.

Constraints

  • 1 <= n <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var distinctIntegers = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Distinct Numbers on Board — Problem & Solution

Count Distinct Numbers on Board solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Count Distinct Numbers on Board is an easy coding problem on math, simulation and number theory, asked in Amazon, TCS and Zoho interviews.

  • Difficulty: Easy
  • Topics: Math, Simulation, Number Theory
  • Asked at: Amazon, TCS, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You write n on a board. Every day, for each number x already on the board, you add every y in [1, n] such that x % y == 1. Numbers never repeat on the board.

Return how many distinct numbers the board holds after 10^9 days.

Example 1

Input: n = 5
Output: 4
Explanation: 5 % 4 = 1 adds 4; then 4 % 3 = 1 adds 3; then 3 % 2 = 1 adds 2. The board ends as {2,3,4,5}.

Example 2

Input: n = 3
Output: 2
Explanation: 3 % 2 = 1 adds 2, and 2 adds nothing new.

Example 3

Input: n = 1
Output: 1
Explanation: 1 % y == 1 has no solution in range, so only 1 stays.

Constraints

  • 1 <= n <= 100

Hints for Count Distinct Numbers on Board

  1. Hint 1

    Simulate the first few days by hand for n = 5 or n = 6 and watch what lands on the board.

  2. Hint 2

    x % (x - 1) == 1 whenever x > 2, so every number pulls in its predecessor.

  3. Hint 3

    That cascade stops at 2, and 1 can never be added — the answer has a one-line form.

How to solve Count Distinct Numbers on Board

For any x > 2, x % (x - 1) == 1, so writing x immediately makes x - 1 appear. Starting from n, the cascade sweeps all the way down to 2, and 1 is unreachable because y would have to exceed x.

Approach

  1. Handle n == 1 separately: the board is just {1}, so the answer is 1.
  2. Otherwise the board becomes {2, 3, …, n}, which has n - 1 numbers.

Why it works

By induction every x in [3, n] adds x - 1, so all of 2 … n appear. And 1 never does: x % y == 1 requires y > 1 and x > y, so the value added is always at least 2. Nothing outside [1, n] is ever considered.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • Actually simulating 10^9 days is a trap — the board stabilises within n steps.
  • n = 1 is the only case where the answer is not n - 1.

Reference solution

Python

def distinctIntegers(n: int) -> int:
    return 1 if n == 1 else n - 1

Java

public static int distinctIntegers(int n) {
    return n == 1 ? 1 : n - 1;
}

C++

int distinctIntegers(int n) {
    return n == 1 ? 1 : n - 1;
}

JavaScript

var distinctIntegers = function(n) {
    return n === 1 ? 1 : n - 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue