Count Distinct Numbers on Board

Count Distinct Numbers on Board

What is this problem about?

In the Count Distinct Numbers on Board coding problem, you start with a number n on a board. Every day, for every number x already on the board, you check all numbers i from 1 to n. If x % i == 1, you add i to the board. You need to find how many distinct numbers will be on the board after 10^9 days.

Why is this asked in interviews?

Oracle uses the Count Distinct Numbers on Board interview question to test your ability to look past a complex description and find a simple pattern. It’s an "Easy" problem that evaluates if you can identify that the process eventually adds almost all numbers to the board. It’s a test of logical reasoning over coding complexity.

Algorithmic pattern used

This is a Simulation / Observation problem.

1. If you have x on the board, then x - 1 will eventually be added because x % (x - 1) == 1 (for x > 2).
2. Once x - 1 is on the board, x - 2 will be added.
3. This continues until you reach 2.
4. Therefore, all numbers from 2 to n will eventually be on the board.
5. If n > 1, the answer is n - 1. If n = 1, the answer is 1.

Example explanation

n = 5

1. Day 1: Board = {5}.
2. 5 % 4 == 1. Add 4. Board = {5, 4}.
3. Day 2: 4 % 3 == 1. Add 3. Board = {5, 4, 3}.
4. Day 3: 3 % 2 == 1. Add 2. Board = {5, 4, 3, 2}. Total distinct numbers = 4. Result: 5 - 1 = 4.

Common mistakes candidates make

• Literal Simulation: Trying to run the simulation for 10^9 days, which is obviously impossible.
• Nested Loops: Writing an O(N^2) loop to simulate the process when the answer is O(1).
• Handling n=1: Forgetting that if you start with 1, no other numbers can satisfy the modulo condition.

Interview preparation tip

Whenever an interview question mentions a ridiculously large number like "10^9 days" or "10^9 operations," it's a huge hint that the answer is either a mathematical formula or a constant value.