You are given a positive integer n, that is initially placed on a board. Every day, for 109 days, you perform the following procedure:
x present on the board, find all numbers 1 <= i <= n such that x % i == 1.Return the number of distinct integers present on the board after 109 days have elapsed.
Note:
% 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 <= 100Problem Overview: You start with a single integer n written on a board. Each day you choose an existing number x and add a number i such that x % i == 1. The process repeats until no new numbers can appear. The goal is to return how many distinct integers will eventually be on the board.
Approach 1: Simulation and Observation (Time: O(n^2), Space: O(n))
The most direct way is to simulate the process. Maintain a set of numbers currently on the board and repeatedly try every possible pair (x, i) where x is on the board and 1 ≤ i ≤ n. If x % i == 1, add i to the set. Continue until an iteration produces no new numbers. A hash set ensures duplicates are ignored and membership checks stay O(1). This approach clearly models the rules and helps reveal the underlying pattern, but it performs many redundant checks as the board grows.
During simulation you quickly notice a pattern: once a number x is present, the condition x % (x-1) == 1 always holds. That means if x exists, x-1 will eventually be added. Starting from n, this chain continues downward and gradually generates every number until reaching 2. Using a hash table (set) keeps the implementation simple while the simulation runs.
Approach 2: Reverse Calculation Method (Math Insight) (Time: O(1), Space: O(1))
The key observation removes the need for simulation entirely. From any number x ≥ 2, choosing i = x - 1 satisfies x % (x - 1) = 1. This guarantees the sequence will eventually produce every integer from n down to 2. The only value that cannot generate a new number is 1, because no valid i satisfies 1 % i = 1. As a result, once the chain reaches 2, the board contains all numbers {2, 3, ..., n}.
The final count becomes simple: if n = 1, only 1 exists, so the answer is 1. For any n ≥ 2, the board will contain every integer from 2 to n, which totals n - 1 distinct values. This converts what looks like a simulation problem into a constant-time math observation.
Recommended for interviews: Start by describing the simulation idea to show you understand the process and constraints. Then explain the mathematical pattern x → x-1 created by the modulo rule. Interviewers expect the constant-time solution because it demonstrates pattern recognition and reasoning about number properties instead of brute force iteration.
This approach works by reverse engineering the board filling process. Given a number n, we find the numbers that can potentially go on the board. These numbers are such that x % i == 1 for each previously existing number x on the board. Through observation, you'll notice that once a number is included on the board, it allows for smaller numbers to be generated. By understanding the modulo behavior, we can establish that the smallest sequence achievable sorts to n, n-1, ..., 2 after limitless days.
The C solution uses a simple function that takes n as an input and returns n-1. This solution works because the process fills out all possible numbers such that 1 <= i < n. For n=5, these are 2, 3, 4.
Time Complexity: O(1)
Space Complexity: O(1)
In this approach, we simulate the process of adding numbers to the board for small values of n to identify a pattern. By listing the numbers that result from x % i == 1, it becomes evident that the upper bound determines the potential set of numbers you can derive. This results in numbers from 2 to n eventually appearing on the board over time.
This C implementation uses a simulation to justify a similar conclusion. By observing patterns from smaller simulations, it simplifies this to the return statement n - 1.
Time Complexity: O(n^2) -- for full simulation
Effective Complexity: O(1) -- after inference
Space Complexity: O(1)
Since every operation on the number n on the desktop will also cause the number n-1 to appear on the desktop, the final numbers on the desktop are [2,...n], that is, n-1 numbers.
Note that n could be 1, so it needs to be specially judged.
The time complexity is O(1), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Reverse Calculation Method | Time Complexity: O(1) |
| Simulation and Observation | Time Complexity: O(n^2) -- for full simulation |
| Lateral Thinking | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation and Observation | O(n^2) | O(n) | When exploring the process or validating the pattern with brute-force simulation |
| Reverse Calculation Method (Math Insight) | O(1) | O(1) | Best solution for interviews and production due to constant time and simple logic |
A. Count Distinct Numbers on Board - LEETCODE WEEKLY CONTEST 330 (Code + Explanation in details) • Joyjit Codes • 983 views views
Watch 9 more video solutions →Practice Count Distinct Numbers on Board with our built-in code editor and test cases.
Practice on FleetCode