Taro Logo

Count Distinct Numbers on Board

Easy
Asked by:
Profile picture
66 views
Topics:
Greedy Algorithms

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

Note:

  • Once a number is placed on the board, it will remain on it until the end.
  • % 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 <= 100

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the maximum possible value of the input integer n?
  2. Is the input n guaranteed to be a positive integer?
  3. Can you provide an example input and the expected output after an infinite number of days, particularly for a smaller value of n?
  4. By 'distinct numbers on the board', do you mean the count of unique numbers that *ever* appear on the board throughout the infinite process, or just the count of unique numbers present at any single point after the process has converged?
  5. Is there a specific data type that should be used for representing the potentially large numbers after many iterations (e.g., 64-bit integer)?

Brute Force Solution

Approach

The basic idea is to simulate the game as described. We start with the initial number on the board, and then for each turn, we consider adding every possible number that can be generated by applying the given rule.

Here's how the algorithm would work step-by-step:

  1. Start with a board containing only the initial number.
  2. For each turn, go through every number that is already on the board.
  3. For each of these numbers, try every number between 1 and the initial number.
  4. If the number we're trying divides the number on the board, and it's not already on the board, add it to the board.
  5. Keep doing this for a very large number of turns to find all possible distinct numbers that can appear on the board.
  6. At the very end, count how many different numbers are on the board.

Code Implementation

def count_distinct_numbers(initial_number):
    numbers_on_board = {initial_number}
    previous_size = 0

    while len(numbers_on_board) != previous_size:
        previous_size = len(numbers_on_board)
        numbers_list = list(numbers_on_board)

        # Iterate through all pairs of numbers on the board
        for i in range(len(numbers_list)):
            for j in range(i + 1, len(numbers_list)):
                first_number = numbers_list[i]
                second_number = numbers_list[j]

                difference = abs(first_number - second_number)

                # Add the difference if it's not already present
                if difference not in numbers_on_board:

                    numbers_on_board.add(difference)

    return len(numbers_on_board)

Big(O) Analysis

Time Complexity
O(n^2) – The outermost loop simulates a large number of turns. Inside this loop, we iterate through all the numbers currently on the board, which can be up to n (the initial number). For each number on the board, we iterate from 1 to n, checking for divisibility. Thus, for each turn, we have a nested loop structure that executes up to n * n times. Since the number of turns to find all possible numbers can be considered a constant factor, the time complexity is dominated by the nested loops which approximate n * n operations, resulting in O(n^2).
Space Complexity
O(N) – The described algorithm maintains a board, which effectively stores the distinct numbers encountered. In the worst-case scenario, every number from 1 to N (the initial number) could potentially be added to the board. This board acts as an auxiliary data structure, implicitly using a set or similar structure to keep track of the distinct numbers. Thus, the space required scales linearly with the input N, resulting in O(N) space complexity.

Optimal Solution

Approach

The key insight is that after the first turn, we'll always add the number 1 to the board if it's not already there. This is because you can always pick 'x' and 'i' as the same number, so 'x mod i' will become 'x mod x' which is zero and then you add one. The game continues until the number 1 appears on the board.

Here's how the algorithm would work step-by-step:

  1. First, check if the number 1 is already on the board.
  2. If the number 1 is already on the board, then there are no new numbers to add, so the count of unique numbers stays the same as the initial number.
  3. If the number 1 is NOT on the board, then you can add the number 1 to the board.
  4. In this case, the count of unique numbers will always become the same as the initial number because all the numbers from 1 to the original number will eventually exist on the board.

Code Implementation

def count_distinct_numbers(number_on_board):
    # If the initial number is 1, the count remains 1
    if number_on_board == 1:
        return 1

    # If the initial number is > 1, '1' will be added eventually.
    return number_on_board

Big(O) Analysis

Time Complexity
O(1) – The algorithm checks if the number 1 exists in the input array of size 'n'. This check involves iterating through the array at most once. However, according to the plain English explanation, the algorithm avoids iterating through the array to determine whether 1 already exists or not. The core logic only involves checking if the number 1 is present and incrementing or not incrementing if the number 1 is not present. These checks are independent of the input size 'n' and take constant time. Therefore, the time complexity is O(1).
Space Complexity
O(1) – The provided explanation doesn't explicitly use any auxiliary data structures. It only checks if the number 1 is present on the board. This can be done without creating any new data structures like lists, sets, or hashmaps. Therefore, the space used is constant, regardless of the input size (the initial number on the board).

Edge Cases

n = 1
How to Handle:
The only divisor of 1 is 1, so the board will always only contain 1; return 1.
n = 2
How to Handle:
The divisors of 2 are 1 and 2; subsequently, only 1 and 2 will ever be on the board, hence, return 2.
n > 2
How to Handle:
For any n greater than 2, 1 and n will always be divisors, and since the process continues infinitely, all numbers from 1 to n will eventually be on the board because numbers will continue breaking down into their smaller divisors, including all those from 1 to n; thus the answer is always n.
Large n causing integer overflow
How to Handle:
Ensure the return type is large enough to hold the maximum possible value of n, preventing integer overflow.
Negative n
How to Handle:
The problem description implies a positive integer, so return 0 or throw an IllegalArgumentException if n < 1, as divisors are not defined for values less than 1 in this context.
n = Integer.MAX_VALUE
How to Handle:
Since the solution returns n, ensure the return type (e.g., long) can accommodate Integer.MAX_VALUE without overflow if necessary.
n = 0
How to Handle:
Since the problem definition implies positive number, throw an IllegalArgumentException or return 0 if n = 0, as 0 has infinite divisors.
Time Complexity for large n
How to Handle:
The solution should have O(1) complexity because it's simply returning n so it will scale well.