Count Distinct Numbers on Board

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.

• 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.

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.

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