algoadvance

Leetcode 2549. Count Distinct Numbers on Board

Problem Statement

A number n is printed on a board. Every second, n is replaced by a number on the board plus the count of distinct numbers already appearing on the board. Return the number shown on the board after it stops changing.

Clarifying Questions

  1. What is the initial value of n?
    • It is provided as input.
  2. When does the number stop changing?
    • The number stops changing if it’s equal to its previous value. This would mean that the count of distinct numbers appearing on the board has saturated.
  3. Should we return the final value of n?
    • Yes, return the value of n when it stops changing.
  4. Are there any constraints on the size of n?
    • This isn’t mentioned explicitly, but it can be assumed to be within the common constraints of integers in programming problems (e.g., 1 ≤ n ≤ 10^9).
  5. Are we allowed to use additional data structures like sets to track distinct numbers?
    • Assuming there’s no restriction against using sets or any other data structures which fit within feasible time and space complexity constraints.

Strategy

  1. Initialize a set to track distinct numbers.
  2. Loop until the number on the board stops changing:
    • Add the current number to the set.
    • Calculate the new number by adding the distinct count (size of the set) to the current number.
    • If the new number equals the current number, break the loop.
  3. Return the current number when the loop exits.

Time Complexity

Code

#include <iostream>
#include <unordered_set>

int countDistinctNumbersOnBoard(int n) {
    std::unordered_set<int> distinctNumbers;
    int previous = -1;
    
    // Loop until the number stops changing
    while (true) {
        distinctNumbers.insert(n);   // Add current number to set
        int newNumber = n + distinctNumbers.size(); // Compute new number

        if (newNumber == n) {
            // If number stops changing, exit loop
            break;
        }
        n = newNumber; // Update current number
    }
    
    return n; // Return stable number on board
}

int main() {
    int n;
    std::cin >> n; // Read initial number
    std::cout << countDistinctNumbersOnBoard(n) << std::endl; // Output result
    return 0;
}

This code takes an initial value n and applies the described transformation until the number stops changing, which happens when adding the count of unique numbers doesn’t alter the current value. The final stable value is then returned.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI