Skip to main content
Talentd

Count Distinct Numbers on Board - Solution & Explanation

EasyArrayHash TableMathSimulation13 min readAsked at: Oracle
Practice this problem

Problem Statement

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

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.

The C solution uses a simple function that takes n as an input and returns n-1. This solution works because the process fills out all possible numbers such that 1 <= i < n. For n=5, these are 2, 3, 4.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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.

This C implementation uses a simulation to justify a similar conclusion. By observing patterns from smaller simulations, it simplifies this to the return statement n - 1.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) -- for full simulation
Effective Complexity: O(1) -- after inference
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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Reverse Calculation Method

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

Simulation and Observation

Time Complexity: O(n^2) -- for full simulation
Effective Complexity: O(1) -- after inference
Space Complexity: O(1)

Lateral Thinking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulation and ObservationO(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

Video Solution

A. Count Distinct Numbers on Board - LEETCODE WEEKLY CONTEST 330 (Code + Explanation in details) • Joyjit Codes • 983 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count Distinct Numbers on Board with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count of Matches in Tournament