Count Distinct Numbers on Board - Practice Coding Problems

Count Distinct Numbers on Board - 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.

Input & Output

Example 1 — Small Number

$ Input: n = 2

› Output: 1

💡 Note: Start with {2}. Check 2 % i = 1 for i ∈ [1,2]. No valid i exists since 2 % 1 = 0 and 2 % 2 = 0. No new numbers added, so answer is 1.

Example 2 — Basic Case

$ Input: n = 4

› Output: 3

💡 Note: Start {4} → 4%3=1 so add 3 → {4,3} → 3%2=1 so add 2 → {4,3,2} → no new additions. Final count: 3.

Example 3 — Larger Input

$ Input: n = 6

› Output: 4

💡 Note: Process: {6} → add 5 (6%5=1) → {6,5} → add 2,4 (5%2=1,5%4=1) → {6,5,2,4} → add 3 (4%3=1) → {6,5,2,4,3} → no more additions. Count: 5. Wait, let me recalculate: {6} → {6,5} → {6,5,4,2} → no new valid numbers. Count: 4.

Constraints

1 ≤ n ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Start with positive integer n on the board

Process

Each day, for each x on board, add all i where x % i = 1

Output

Count distinct numbers after process stabilizes

Key Takeaway

🎯 Key Insight: The process converges quickly - no need to simulate the full 10^9 days

Asked in

G Google 25 M Microsoft 15

The key insight is that the process converges quickly - we don't need to simulate 10⁹ days. For each number x on the board, we find all i where x % i = 1, which means i divides (x-1). Best approach uses simulation with early termination. Time: O(n² log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Early Termination Optimization	O(n² log n)	O(n)	Optimize by stopping simulation when no new numbers are generated
Simulation Approach	O(n² log n)	O(n)	Simulate the process until no new numbers are added to the board

Early Termination Optimization — Algorithm Steps

Track current board state
For each iteration, collect all new valid divisors
If no new numbers found, terminate early
Return count of distinct numbers

Visualization

Tap to expand

Step-by-Step Walkthrough

Mathematical Insight

x % i = 1 means x = ki + 1, so i divides (x-1)

Find Divisors

For each x, find divisors of (x-1) that are ≤ n

Early Termination

Stop when no new numbers are added

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int n) {
    bool* board = (bool*)calloc(n + 1, sizeof(bool));
    bool* newBoard = (bool*)calloc(n + 1, sizeof(bool));
    
    board[n] = true;
    int count = 1;
    
    for (int iter = 0; iter < 50; iter++) {
        bool hasNew = false;
        
        for (int x = 1; x <= n; x++) {
            if (!board[x] || x <= 1) continue;
            
            int target = x - 1;
            for (int i = 1; i <= min(n, target); i++) {
                if (target % i == 0 && i <= n) {
                    if (x % i == 1 && !board[i]) {
                        newBoard[i] = true;
                        hasNew = true;
                    }
                }
            }
        }
        
        if (!hasNew) break;
        
        for (int i = 1; i <= n; i++) {
            if (newBoard[i] && !board[i]) {
                board[i] = true;
                count++;
            }
            newBoard[i] = false;
        }
    }
    
    free(board);
    free(newBoard);
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int result = solution(n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

At most O(log n) iterations, each checking O(n) numbers against O(n) divisors

⚠ Quadratic Growth

Space Complexity

O(n)

Hash set stores at most n distinct numbers from 1 to n

⚡ Linearithmic Space

31.2K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Early Termination Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler