We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Distinct Numbers on Board

Difficulty: Easy

Problem Description

You are given a positive integer n, that is initially placed on a board. Every day, for 10^9 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 10^9 days have elapsed.

Key Insights

  • The only numbers added to the board are those that satisfy the condition x % i == 1.
  • The process halts when no new numbers can be generated, which is relatively quick given the constraints (1 <= n <= 100).
  • The distinct numbers that can appear on the board can be derived from the initial number n through its divisors.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can utilize a simulation approach. We maintain a set to store distinct integers on the board. Starting with the integer n, we iteratively find all integers i such that x % i == 1 for all x currently on the board. We continue this process until no new integers can be added. The algorithm efficiently tracks the integers through a set to ensure all stored numbers are distinct.

Code Solutions

def countDistinctNumbers(n: int) -> int:
    distinct_numbers = set()
    distinct_numbers.add(n)
    current_numbers = {n}

    while current_numbers:
        next_numbers = set()
        for x in current_numbers:
            for i in range(1, n + 1):
                if x % i == 1:
                    next_numbers.add(i)
        current_numbers = next_numbers - distinct_numbers  # Get new numbers only
        distinct_numbers.update(next_numbers)  # Add new numbers to the set

    return len(distinct_numbers)

# Example usage
print(countDistinctNumbers(5))  # Output: 4
← Back to All Questions