#2549

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Distinct Numbers on Board

Compute the number of distinct integers generated on a board using repeated modulo operations over a long sequence of days.

array hash table math simulation

Problem Statement

You are given a positive integer n, initially placed on a board. Each day, for a large number of iterations, you add n % x for every number x currently on the board that is less than n, if the result is not already present.

After all iterations, return the total count of distinct integers on the board. For example, with n = 5, the board eventually contains 2, 3, 4, and 5, totaling 4 distinct numbers.

Examples

Example 1

Input: n = 5

Output: 4

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

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

Solution Approach

Simulate with Hash Set

Maintain a hash set to store current board numbers and iterate through each number to add new modulo results. Continue until no new numbers are added. This approach mirrors the problem pattern of array scanning plus hash lookup.

Use Observed Number Patterns

Notice that for any n > 2, n % (n - 1) == 1, so n - 1 will always be added. Using this pattern reduces the need to simulate every day and quickly fills the board with all numbers down to 2.

Finalize Board Count

Once no new numbers are added, the hash set contains all distinct numbers. Return its size as the answer, efficiently capturing the problem's core pattern without brute-force for a billion days.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on n since the simulation can add up to n - 1 numbers. Space complexity is O(n) for the hash set storing distinct numbers.

What Interviewers Usually Probe

Look for recognition of the n % (n - 1) pattern to shortcut iterations.
Expect discussion on hash set usage to track distinct numbers efficiently.
Candidate may suggest stopping simulation when no new numbers appear, showing understanding of growth limits.

Common Pitfalls or Variants

Common pitfalls

Attempting to simulate a billion days literally rather than leveraging patterns.
Forgetting to check if modulo results are already in the board set, causing duplicates.
Miscounting initial number n or neglecting small numbers like 2 and 1 if n is small.

Follow-up variants

Compute distinct numbers for a board starting with multiple initial integers.
Return the sorted list of distinct numbers instead of just the count.
Change the modulo operation to a different arithmetic function and compute distinct results.

FAQ

What is the easiest way to track numbers for Count Distinct Numbers on Board?

Use a hash set to store numbers as they are generated and check for new additions each iteration.

Do I need to simulate a billion days literally?

No, recognizing that n % (n - 1) == 1 allows the board to reach all numbers down to 2 quickly without full simulation.

Can this problem be solved without hash sets?

Yes, but using a hash set prevents duplicates and directly captures the array scanning plus hash lookup pattern efficiently.

What is the expected time complexity?

O(n) in practice since the board can only grow up to n - 1 distinct numbers and each number is processed once.

Does the solution change for small n values like 1 or 2?

Yes, for n = 1 or 2, the board quickly stabilizes with fewer distinct numbers, but the pattern and hash tracking approach remains the same.

terminal

Solution

Solution 1: Lateral Thinking

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.

1

2

3

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

Continue Practicing

#2521 distinct prime factors of product of array #2584 split the array to make coprime products #2593 find score of an array after marking all elements