Count Distinct Numbers on Board

Easy

#2329Time: O(1), as it only involves a single conditional check.Space: O(1), as no extra space is required.

Patterns

Data structures

Prompt

You are given a positive integer n, that is initially placed on a board. Every day, for 10⁹ days, you perform the following procedure:

For each number x present on the board, find all numbers 1 <= i <= n such that x % i == 1.
Then, place those numbers on the board.

Return the number of distinct integers present on the board after 10⁹ days have elapsed.

Note:

Once a number is placed on the board, it will remain on it until the end.
% stands for the modulo operation. For example, 14 % 3 is 2.

Example 1:

Input: n = 5
Output: 4
Explanation: Initially, 5 is present on the board. 
The next day, 2 and 4 will be added since 5 % 2 == 1 and 5 % 4 == 1. 
After that day, 3 will be added to the board because 4 % 3 == 1. 
At the end of a billion days, the distinct numbers on the board will be 2, 3, 4, and 5.

Example 2:

Input: n = 3
Output: 2
Explanation: 
Since 3 % 2 == 1, 2 will be added to the board. 
After a billion days, the only two distinct numbers on the board are 2 and 3.

Constraints:

1 <= n <= 100

Approaches

3 approaches with complexity analysis and trade-offs.

The most efficient approach comes from a mathematical observation of the problem's rules. By analyzing the condition x % i == 1, we can deduce a pattern that reveals the final state of the board without any simulation. The large number of days (10^9) is a strong hint that the system reaches a predictable fixed point quickly.

Algorithm

Analyze the condition x % i == 1. This implies i is a divisor of x - 1 and i > 1.
If n > 2, then n-1 is a valid choice for i since n % (n-1) == 1 and 2 <= n-1 <= n. Thus, n-1 is added to the board.
If a number k >= 3 is on the board, k-1 will be added because k % (k-1) == 1.
This creates a chain reaction: n places n-1, n-1 places n-2, ..., 3 places 2.
The chain stops at 2, as 2-1=1 has no divisors greater than 1.
So for n > 2, all numbers from 2 to n will eventually be on the board. The count is n-1.
For n=1 or n=2, this chain reaction does not start. The board will only contain the initial number. The count is 1.
The final logic is: if n <= 2, return 1; otherwise, return n-1.

Walkthrough

Let's analyze the core rule: a number i is placed on the board if x % i == 1 for some x already on the board. This is only possible if i > 1.

Case 1: n > 2

Initially, n is on the board. Let's check if n-1 can be added. We test x=n and i=n-1. The condition is n % (n-1) == 1, which is true. Since n > 2, we have n-1 >= 2, so i=n-1 is a valid number to be placed on the board.
Now, n-1 is on the board. If n-1 > 2 (i.e., n > 3), we can similarly show that n-2 will be added.
This establishes a chain reaction: n causes n-1 to be added, which causes n-2 to be added, and so on, all the way down to 3 causing 2 to be added.
Once 2 is on the board, it cannot add any new numbers, because 2 % i == 1 requires i to be a divisor of 2-1=1, and no such i > 1 exists.
Therefore, for any n > 2, the board will eventually contain all integers from 2 to n. The total count of these numbers is n - 2 + 1 = n-1.

Case 2: n <= 2

If n=1 or n=2, the chain reaction described above never starts. No number i > 1 satisfies n % i == 1. Thus, the board only ever contains the initial number. The count is 1.

This leads to a very simple O(1) solution.

1class Solution {2    public int distinctIntegers(int n) {3        // If n is 1 or 2, no new numbers can be added.4        // For n=1, 1%i==1 is impossible.5        // For n=2, 2%i==1 requires i to be a divisor of 1, so i=1, but we need i>1.6        if (n <= 2) {7            return 1;8        }9        // If n > 2, n-1 is added, which adds n-2, ..., until 2 is added.10        // The final set of numbers is {2, 3, ..., n}.11        // The size of this set is n-1.12        return n - 1;13    }14}

Complexity

Time

O(1), as it only involves a single conditional check.

Space

O(1), as no extra space is required.

Trade-offs

Pros

Extremely efficient with constant time and space complexity.
Provides a complete solution by understanding the problem's core mechanics.
Simple and elegant implementation.

Cons

Requires a logical deduction and mathematical insight rather than direct implementation of the problem statement.

This approach directly translates the problem description into code. It simulates the process day by day. A HashSet is used to keep track of the distinct numbers on the board. The simulation runs for a sufficient number of iterations (at most n, since the board size is limited by n) until the set of numbers on the board no longer changes, indicating a stable state.

Algorithm

Initialize a HashSet<Integer> called board and add n to it.
Loop for a number of days. A safe upper bound is n iterations, as the board size cannot exceed n and must grow by at least one in each non-stable step.
In each iteration, create a temporary list of numbers to add, newNumbers.
Iterate through a snapshot of the numbers currently on the board.
For each number x on the board, iterate i from 1 to n.
If x % i == 1, add i to the newNumbers set.
After checking all numbers on the board, add all numbers from newNumbers to the main board set.
If the size of the board set did not change in an iteration, the state has stabilized, and we can break the loop early.
Finally, return the size of the board set.

Walkthrough

We start with a HashSet containing only the integer n. We then enter a loop that simulates the passage of days. In each 'day', we iterate through all the numbers x currently present on our board. For each x, we check every integer i from 1 to n to see if it satisfies the condition x % i == 1. All such integers i are collected. After checking all x's, these collected integers are added to our main HashSet. This process repeats. Since the numbers that can be added are limited to the range [1, n], the set of numbers on the board will eventually stop growing. We can detect this stabilization by checking if the size of the set increases after a day's operations. If it doesn't, we can stop the simulation and return the size of the set. A loop of n iterations is a safe upper bound for this stabilization to occur.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int distinctIntegers(int n) {6        Set<Integer> board = new HashSet<>();7        board.add(n);8 9        // The process will stabilize in at most n steps.10        for (int day = 0; day < n + 1; day++) {11            Set<Integer> newNumbers = new HashSet<>();12            for (int x : board) {13                for (int i = 1; i <= n; i++) {14                    if (x % i == 1) {15                        newNumbers.add(i);16                    }17                }18            }19            20            int initialSize = board.size();21            board.addAll(newNumbers);22            // If no new numbers were added, the board is stable.23            if (board.size() == initialSize) {24                break;25            }26        }27        28        return board.size();29    }30}

Complexity

Time

O(n^3). The outer loop can run up to `n` times. Inside, we iterate over the board (size up to `n`), and for each element, we loop `i` from 1 to `n`. This results in a cubic time complexity.

Space

O(n) to store the numbers on the board in the `HashSet`.

Trade-offs

Pros

Simple to understand as it directly models the process described in the problem.
Guaranteed to be correct if implemented properly.

Cons

Highly inefficient due to multiple nested loops.
The simulation over many days is unnecessary as the state stabilizes quickly.
Fails to recognize the simple underlying pattern of the problem.

Instead of simulating day-by-day, we can reframe the problem as finding all reachable nodes in a graph starting from node n. A number i is reachable from x if x % i == 1. This can be efficiently solved using a Breadth-First Search (BFS) algorithm. We use a queue to keep track of numbers we need to process and a set to store the numbers we've already found (and visited).

Algorithm

Initialize a HashSet<Integer> board to store the results and act as a visited set.
Initialize a Queue<Integer> queue to manage the numbers to be processed.
Add the starting number n to both the board and the queue.
While the queue is not empty:
- Dequeue a number x.
- Iterate i from 1 to n.
- If x % i == 1 and i is not yet on the board:
  - Add i to the board set.
  - Enqueue i for future processing.
When the queue is empty, all reachable numbers have been found. Return the size of the board set.

Walkthrough

This approach treats the problem as a graph traversal. The numbers from 1 to n are the nodes. A directed edge exists from x to i if i can be generated from x. We start our traversal from n. We use a queue to implement BFS and a set to keep track of visited nodes (the numbers on the board). Initially, n is added to both the queue and the set. We then repeatedly extract a number x from the queue, find all new numbers i it can generate (x % i == 1), and for any i that hasn't been visited yet, we add it to the set and the queue. This process continues until the queue is empty, at which point we have found all distinct numbers that can ever appear on the board. The final answer is the size of the set.

1import java.util.HashSet;2import java.util.Set;3import java.util.Queue;4import java.util.LinkedList;5 6class Solution {7    public int distinctIntegers(int n) {8        Set<Integer> board = new HashSet<>();9        Queue<Integer> queue = new LinkedList<>();10 11        board.add(n);12        queue.add(n);13 14        while (!queue.isEmpty()) {15            int x = queue.poll();16            for (int i = 1; i <= n; i++) {17                if (x % i == 1) {18                    // .add() returns true if the element was new to the set19                    if (board.add(i)) { 20                        queue.add(i);21                    }22                }23            }24        }25        return board.size();26    }27}

Complexity

Time

O(n^2). Each number from 1 to `n` is enqueued and processed at most once. Processing a number involves a loop from 1 to `n`.

Space

O(n) for the `HashSet` and the `Queue`. In the worst case, most numbers from 1 to `n` could be added.

Trade-offs

Pros

Much more efficient than the direct simulation.
Avoids redundant computations by processing each number only once.

Cons

While more efficient than brute-force, it is still not optimal.
It performs unnecessary computations compared to the mathematical solution.

Solutions

Solution

1class Solution {2public3  int distinctIntegers(int n) { return Math.max(1, n - 1); }4}

1class Solution {2public:3  int distinctIntegers(int n) { return max(1, n - 1); }4};

1class Solution:2    def distinctIntegers(self, n: int) -> int: return max(1, n - 1)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int distinctIntegers(int n) { return Math.max(1, n - 1); }4}

1class Solution {2public:3  int distinctIntegers(int n) { return max(1, n - 1); }4};

1class Solution:2    def distinctIntegers(self, n: int) -> int: return max(1, n - 1)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.