2549. Count Distinct Numbers on Board Solution

Q: Is Count Distinct Numbers on Board easy or hard?

LeetCode classifies this problem as Easy. The challenge is not implementation but recognizing the mathematical pattern behind the modulo rule. Once the observation is clear, the final code is only one or two lines.

Q: Count Distinct Numbers on Board Python/Java solution

Most implementations return a simple conditional: if n == 1 return 1, otherwise return n - 1. This constant-time logic works in Python, Java, C++, C#, and JavaScript since the solution relies only on arithmetic reasoning.

Q: How to solve Count Distinct Numbers on Board in O(1)?

Observe that any number x >= 2 can generate x - 1 because x % (x - 1) equals 1. Starting from n, the process keeps producing numbers down to 2. That means the board eventually contains {2, 3, ..., n}. The result is n - 1 when n > 1, otherwise 1.

The problem

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

Approach overview

Problem Overview: You start with a single integer n written on a board. Each day you choose an existing number x and add a number i such that x % i == 1. The process repeats until no new numbers can appear. The goal is to return how many distinct integers will eventually be on the board.

Approach 1: Simulation and Observation (Time: O(n^2), Space: O(n))

The most direct way is to simulate the process. Maintain a set of numbers currently on the board and repeatedly try every possible pair (x, i) where x is on the board and 1 ≤ i ≤ n. If x % i == 1, add i to the set. Continue until an iteration produces no new numbers. A hash set ensures duplicates are ignored and membership checks stay O(1). This approach clearly models the rules and helps reveal the underlying pattern, but it performs many redundant checks as the board grows.

During simulation you quickly notice a pattern: once a number x is present, the condition x % (x-1) == 1 always holds. That means if x exists, x-1 will eventually be added. Starting from n, this chain continues downward and gradually generates every number until reaching 2. Using a hash table (set) keeps the implementation simple while the simulation runs.

Approach 2: Reverse Calculation Method (Math Insight) (Time: O(1), Space: O(1))

The key observation removes the need for simulation entirely. From any number x ≥ 2, choosing i = x - 1 satisfies x % (x - 1) = 1. This guarantees the sequence will eventually produce every integer from n down to 2. The only value that cannot generate a new number is 1, because no valid i satisfies 1 % i = 1. As a result, once the chain reaches 2, the board contains all numbers {2, 3, ..., n}.

The final count becomes simple: if n = 1, only 1 exists, so the answer is 1. For any n ≥ 2, the board will contain every integer from 2 to n, which totals n - 1 distinct values. This converts what looks like a simulation problem into a constant-time math observation.

Recommended for interviews: Start by describing the simulation idea to show you understand the process and constraints. Then explain the mathematical pattern x → x-1 created by the modulo rule. Interviewers expect the constant-time solution because it demonstrates pattern recognition and reasoning about number properties instead of brute force iteration.

Approach 1: Reverse Calculation Method

This approach works by reverse engineering the board filling process. Given a number n, we find the numbers that can potentially go on the board. These numbers are such that x % i == 1 for each previously existing number x on the board. Through observation, you'll notice that once a number is included on the board, it allows for smaller numbers to be generated. By understanding the modulo behavior, we can establish that the smallest sequence achievable sorts to n, n-1, ..., 2 after limitless days.

Python

def count_distinct_numbers(n):
    return n - 1

n = 5
print(count_distinct_numbers(n))

Java

public class DistinctNumbers {
    public static int countDistinctNumbers(int n) {
        return n - 1;
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println(countDistinctNumbers(n));
    }
}

C++

#include <iostream>

int countDistinctNumbers(int n) {
    return n - 1;
}

int main() {
    int n = 5;
    std::cout << countDistinctNumbers(n);
    return 0;
}

JavaScript

function countDistinctNumbers(n) {
    return n - 1;
}

let n = 5;
console.log(countDistinctNumbers(n));

#include <stdio.h>

int countDistinctNumbers(int n) {
    return n - 1;
}

int main() {
    int n = 5;
    printf("%d", countDistinctNumbers(n));
    return 0;
}

using System;

class Program {
    static int CountDistinctNumbers(int n) {
        return n - 1;
    }

    static void Main() {
        int n = 5;
        Console.WriteLine(CountDistinctNumbers(n));
    }
}

The Python solution implements the same logic but in Python syntax, effectively demonstrating the counting of distinct numbers using the n-1 logic.

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Simulation and Observation

In this approach, we simulate the process of adding numbers to the board for small values of n to identify a pattern. By listing the numbers that result from x % i == 1, it becomes evident that the upper bound determines the potential set of numbers you can derive. This results in numbers from 2 to n eventually appearing on the board over time.

Python

def simulate_process(n):
    if n == 1:
        return 1
    return n - 1

n = 5
print(simulate_process(n))

Java

public class Simulation {
    public static int simulateProcess(int n) {
        if (n == 1) return 1;
        return n - 1;
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println(simulateProcess(n));
    }
}

C++

#include <iostream>

int simulateProcess(int n) {
    if (n == 1) return 1;
    return n - 1;
}

int main() {
    int n = 5;
    std::cout << simulateProcess(n);
    return 0;
}

JavaScript

function simulateProcess(n) {
    if (n == 1) return 1;
    return n - 1;
}

let n = 5;
console.log(simulateProcess(n));

#include <stdio.h>

int simulateProcess(int n) {
    if (n == 1) return 1;
    return n - 1;
}

int main() {
    int n = 5;
    printf("%d", simulateProcess(n));
    return 0;
}

using System;

class Simulation {
    static int SimulateProcess(int n) {
        if (n == 1) return 1;
        return n - 1;
    }

    static void Main() {
        int n = 5;
        Console.WriteLine(SimulateProcess(n));
    }
}

The Python code reinforces the conclusion that simulation leads us to streamline the computation to a direct arithmetic operation once general patterns become clear.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: 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.

Note that n could be 1, so it needs to be specially judged.

The time complexity is O(1), and the space complexity is O(1).

TypeScript

function distinctIntegers(n: number): number {
    return Math.max(1, n - 1);
}

func distinctIntegers(n int) int {
	return max(1, n-1)
}

Rust

impl Solution {
    pub fn distinct_integers(n: i32) -> i32 {
        (1).max(n - 1)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Reverse Calculation Method	Time Complexity: O(1) Space Complexity: O(1)
Simulation and Observation	Time Complexity: O(n^2) Space Complexity: O(1)
Lateral Thinking	–

Complexity analysis

Approach	Time	Space	When to Use
Simulation and Observation	O(n^2)	O(n)	When exploring the process or validating the pattern with brute-force simulation
Reverse Calculation Method (Math Insight)	O(1)	O(1)	Best solution for interviews and production due to constant time and simple logic

Frequently asked questions

Is Count Distinct Numbers on Board easy or hard?

LeetCode classifies this problem as Easy. The challenge is not implementation but recognizing the mathematical pattern behind the modulo rule. Once the observation is clear, the final code is only one or two lines.

Count Distinct Numbers on Board Python/Java solution

Most implementations return a simple conditional: if n == 1 return 1, otherwise return n - 1. This constant-time logic works in Python, Java, C++, C#, and JavaScript since the solution relies only on arithmetic reasoning.

How to solve Count Distinct Numbers on Board in O(1)?

Observe that any number x >= 2 can generate x - 1 because x % (x - 1) equals 1. Starting from n, the process keeps producing numbers down to 2. That means the board eventually contains {2, 3, ..., n}. The result is n - 1 when n > 1, otherwise 1.

What is the best approach for Count Distinct Numbers on Board?

The optimal approach uses a mathematical observation. If n >= 2, the process always generates every number from 2 to n because x % (x-1) = 1. Therefore the number of distinct integers on the board becomes n - 1. This leads to an O(1) time and O(1) space solution.

Is Count Distinct Numbers on Board asked at Google/Amazon/Meta?

This problem is categorized as an easy mathematical reasoning problem and commonly appears in practice sets for companies like Google, Amazon, and Meta. It tests pattern recognition and the ability to simplify simulations using math insights.

What data structure is used in Count Distinct Numbers on Board?

A hash set is typically used in the simulation approach to store distinct numbers and avoid duplicates. However, the optimal mathematical solution does not require any data structure because the result is computed directly.

What is the time complexity of Count Distinct Numbers on Board?

The optimal solution runs in O(1) time because the answer can be derived directly from the input n. A brute-force simulation approach takes roughly O(n^2) time since it repeatedly checks possible pairs of numbers and divisors.

Count Distinct Numbers on Board solution and explanation

The problem

Approach overview

Approach 1: Reverse Calculation Method

Approach 2: Simulation and Observation

Approach 3: Lateral Thinking

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Distinct Numbers on Board solution and explanation

The problem

Approach overview

Approach 1: Reverse Calculation Method

Approach 2: Simulation and Observation

Approach 3: Lateral Thinking

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems