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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Distinct Numbers on Board

Number: 2679

Difficulty: Easy

Paid? No

Companies: Oracle

Problem Description

Given a positive integer n that is initially placed on a board, every day for 10^9 days we perform the following procedure: for every number x on the board, for each integer i in the range [1, n] check if x % i == 1; if the condition holds, place i on the board. Once a number appears on the board, it stays there. Return the number of distinct integers on the board after 10^9 days.

Key Insights

  • The board eventually becomes stable long before 10^9 days because n is small (n ≤ 100).
  • We can simulate the process using BFS/iterative expansion over the set of numbers on the board.
  • For each number x on the board, traverse all integers in [1, n] and add i if x % i == 1 and i is not already present.
  • If n is 1, the board remains {1} since no i satisfies 1 % i == 1 for i > 1.
  • The process is essentially a graph expansion where each number x leads to its “neighbors” i satisfying the modulo condition.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case where n is at most 100. Space Complexity: O(n), because we store at most n numbers.

Solution

We can solve the problem by simulating the spread of numbers on the board using a set to keep track of all distinct numbers and a queue (or list) for the current numbers that can generate new numbers. Begin with the initial number n. For each number x in the queue, iterate from 1 to n and check if x % i == 1. If the condition holds and i is not in the set, add it to the board and the queue. Continue until no new numbers are added. Finally, the answer is the number of elements in the board.

Code Solutions

# Python solution using BFS with comments

def countDistinctNumbers(n: int) -> int:
    # Create a set to hold distinct numbers on the board
    board = set()
    # Use a list as the queue for numbers to process
    queue = []
    
    # Initially, add the given number n to the board and queue
    board.add(n)
    queue.append(n)
    
    # Process until no new numbers can be added
    while queue:
        # Remove the first element from the queue
        current = queue.pop(0)
        # Check every integer i from 1 to n
        for i in range(1, n + 1):
            # If condition is met and the number is not already in the board
            if current % i == 1 and i not in board:
                board.add(i)
                queue.append(i)
    
    # Return the number of distinct numbers present on the board
    return len(board)

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