LeetCode 2549 - Count Distinct Numbers on Board

LeetCode Problem 2549

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Math, Simulation

Solution

Problem Understanding

The problem starts with a single integer n written on a board. Every day, we examine every number currently on the board. For each number x, we look for all integers i such that:

• 1 <= i <= n
• x % i == 1

Whenever such an integer i exists, we add it to the board. Numbers are never removed, and duplicates do not matter because the final answer asks for the number of distinct integers present after a very large number of days.

Even though the simulation lasts for 10^9 days, the important observation is that the process stabilizes very quickly. The task is to determine how many unique integers can eventually appear on the board.

The input consists of a single positive integer n, where:

1 <= n <= 100

The output is a single integer representing the total number of distinct integers that will exist on the board after the process has fully stabilized.

The small constraint suggests that even brute force simulation would technically work, but the problem is designed around discovering a mathematical pattern rather than implementing a long simulation.

One important edge case is when n = 1. Since there is no integer i satisfying:

1 % i == 1

for any valid i, the board never changes. The answer remains 1.

Another subtle point is that the process only adds numbers smaller than the current number. This means the board gradually fills downward toward 2, but never reaches 1 except when n already starts as 1.

Approaches

Brute Force Simulation

The straightforward approach is to simulate the process exactly as described.

We maintain a set containing all distinct numbers currently on the board. For every number x in the set, we test every integer i from 1 to n. If:

x % i == 1

then we add i to the set.

We repeat this process until no new numbers are added.

This approach is correct because it directly follows the rules of the problem. Eventually, the set stabilizes because only integers from 1 to n can ever appear.

However, this solution is unnecessarily complicated for such a simple mathematical pattern. Even though n <= 100 makes it feasible, the repeated modular checks are wasteful.

Key Insight

The critical observation is that every integer from 2 through n will eventually appear on the board whenever n > 1.

Why?

For any integer x > 2:

x % (x - 1) == 1

This means that if x is on the board, then x - 1 will eventually be added.

Starting from n, we can repeatedly generate:

n - 1
n - 2
n - 3
...
2

But 1 can never be generated because:

x % 1 == 0

for every integer x.

Therefore:

• If n == 1, only {1} exists, answer is 1
• Otherwise, all integers from 2 to n appear, giving n - 1 distinct integers

This leads to a constant time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Simulates the entire process using a set
Optimal	O(1)	O(1)	Uses the mathematical observation that all numbers from 2 to n appear

Algorithm Walkthrough

Optimal Algorithm

1. Check whether n equals 1.

This is the only special case in the problem. If the board starts with 1, no additional numbers can ever be generated because 1 % i is never 1 for any valid i. 2. If n == 1, return 1.

The board permanently contains only the number 1. 3. Otherwise, return n - 1.

Starting from n, the process repeatedly generates smaller integers because:

x % (x - 1) == 1

Therefore:

n -> n - 1 -> n - 2 -> ... -> 2

Every integer from 2 through n eventually appears.

Why it works

The key invariant is that any integer greater than 2 can generate its immediate predecessor. Since the board starts with n, repeated applications of the modulo rule guarantee that every number down to 2 will eventually be added. The number 1 can never be generated because modulo by 1 always produces 0, never 1. Therefore, the final set contains exactly:

{2, 3, ..., n}

when n > 1.

Python Solution

class Solution:
    def distinctIntegers(self, n: int) -> int:
        if n == 1:
            return 1
        
        return n - 1

The implementation directly encodes the mathematical observation discovered in the analysis.

The first condition handles the special case where the board starts with 1. In that situation, no new numbers can ever be added, so the answer is simply 1.

For every other value of n, the algorithm returns n - 1 because all integers from 2 through n will eventually appear on the board.

The solution does not require simulation, sets, loops, or extra memory because the behavior of the process can be fully characterized mathematically.

Go Solution

func distinctIntegers(n int) int {
    if n == 1 {
        return 1
    }

    return n - 1
}

The Go implementation follows the exact same logic as the Python solution.

Go uses explicit braces and typed integer parameters, but otherwise the algorithm remains identical. Since the constraints are extremely small and the result is always within integer range, there are no overflow concerns.

No slices, maps, or additional data structures are needed because the mathematical observation completely eliminates the need for simulation.

Worked Examples

Example 1

Input: n = 5

Initially, the board contains:

Day	Numbers on Board
0	{5}

Now process the numbers:

• 5 % 2 == 1, add 2
• 5 % 4 == 1, add 4

Day	Numbers on Board
1	{2, 4, 5}

Next iteration:

• 4 % 3 == 1, add 3

Day	Numbers on Board
2	{2, 3, 4, 5}

Further iterations add nothing new.

Final distinct integers:

{2, 3, 4, 5}

Answer:

4

The formula also gives:

n - 1 = 5 - 1 = 4

Example 2

Input: n = 3

Initial state:

Day	Numbers on Board
0	{3}

Processing 3:

• 3 % 2 == 1, add 2

Day	Numbers on Board
1	{2, 3}

No further numbers can be added.

Final distinct integers:

{2, 3}

Answer:

2

The formula gives:

n - 1 = 3 - 1 = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a single conditional check is performed
Space	O(1)	No additional data structures are used

The algorithm runs in constant time because it does not depend on the size of n. The mathematical pattern allows the answer to be computed immediately. Space usage is also constant because the implementation stores only a few integer values.

Test Cases

solution = Solution()

assert solution.distinctIntegers(1) == 1  # Minimum input, nothing can be added
assert solution.distinctIntegers(2) == 1  # Only number 2 remains
assert solution.distinctIntegers(3) == 2  # Example case from prompt
assert solution.distinctIntegers(4) == 3  # Generates 2, 3, 4
assert solution.distinctIntegers(5) == 4  # Example case from prompt
assert solution.distinctIntegers(10) == 9  # General larger value
assert solution.distinctIntegers(100) == 99  # Maximum constraint

Test	Why
n = 1	Validates the special edge case
n = 2	Smallest value where the formula n - 1 applies
n = 3	Confirms the first example
n = 4	Verifies downward generation behavior
n = 5	Confirms the second example
n = 10	Tests a larger normal case
n = 100	Validates behavior at the maximum constraint

Edge Cases

Edge Case 1, n = 1

This is the most important special case in the problem. A naive implementation might incorrectly return 0 because no new numbers are generated. However, the original number remains on the board permanently, so the correct answer is 1.

The implementation handles this explicitly with:

if n == 1:
    return 1

Edge Case 2, Small Values Like n = 2

For n = 2, the process does not generate additional distinct numbers beyond 2 itself. Since the valid set becomes {2}, the answer is 1.

This case validates that the formula should return n - 1, not n.

Edge Case 3, Maximum Constraint n = 100

Even though the constraints are small, this case confirms that the mathematical approach scales perfectly and avoids unnecessary simulation.

A brute force solution would still work, but the optimized implementation computes the result instantly regardless of input size.