Watch 10 video solutions for Count Distinct Numbers on Board, a easy level problem involving Array, Hash Table, Math. This walkthrough by Joyjit Codes has 983 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |