Scale Engineer

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
Math
Data structures
ArrayHash Table

Prompt

You are given a positive integer n, that is initially placed on a board. Every day, for 109 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 109 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.

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;    }}

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.

Solutions

class Solution {public  int distinctIntegers(int n) { return Math.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 →

Next problem