# Count Distinct Numbers on Board
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-distinct-numbers-on-board)
Canonical: https://scaleengineer.com/dsa/problems/count-distinct-numbers-on-board
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Hash Table
---
## Problem
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`

# Approaches
## Brute-Force Simulation
This approach directly translates the problem description into code. It simulates the process day by day. A `HashSet` is used to keep track of the distinct numbers on the board. The simulation runs for a sufficient number of iterations (at most `n`, since the board size is limited by `n`) until the set of numbers on the board no longer changes, indicating a stable state.
**Time:** O(n^3). The outer loop can run up to `n` times. Inside, we iterate over the board (size up to `n`), and for each element, we loop `i` from 1 to `n`. This results in a cubic time complexity. · **Space:** O(n) to store the numbers on the board in the `HashSet`.
**Pros:** Simple to understand as it directly models the process described in the problem.; Guaranteed to be correct if implemented properly.
**Cons:** Highly inefficient due to multiple nested loops.; The simulation over many days is unnecessary as the state stabilizes quickly.; Fails to recognize the simple underlying pattern of the problem.
### Explanation
We start with a `HashSet` containing only the integer `n`. We then enter a loop that simulates the passage of days. In each 'day', we iterate through all the numbers `x` currently present on our board. For each `x`, we check every integer `i` from 1 to `n` to see if it satisfies the condition `x % i == 1`. All such integers `i` are collected. After checking all `x`'s, these collected integers are added to our main `HashSet`. This process repeats. Since the numbers that can be added are limited to the range `[1, n]`, the set of numbers on the board will eventually stop growing. We can detect this stabilization by checking if the size of the set increases after a day's operations. If it doesn't, we can stop the simulation and return the size of the set. A loop of `n` iterations is a safe upper bound for this stabilization to occur.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int distinctIntegers(int n) {
        Set<Integer> board = new HashSet<>();
        board.add(n);

        // The process will stabilize in at most n steps.
        for (int day = 0; day < n + 1; day++) {
            Set<Integer> newNumbers = new HashSet<>();
            for (int x : board) {
                for (int i = 1; i <= n; i++) {
                    if (x % i == 1) {
                        newNumbers.add(i);
                    }
                }
            }
            
            int initialSize = board.size();
            board.addAll(newNumbers);
            // If no new numbers were added, the board is stable.
            if (board.size() == initialSize) {
                break;
            }
        }
        
        return board.size();
    }
}
```
### Algorithm
*   Initialize a `HashSet<Integer>` called `board` and add `n` to it.
*   Loop for a number of days. A safe upper bound is `n` iterations, as the board size cannot exceed `n` and must grow by at least one in each non-stable step.
*   In each iteration, create a temporary list of numbers to add, `newNumbers`.
*   Iterate through a snapshot of the numbers currently on the `board`.
*   For each number `x` on the board, iterate `i` from 1 to `n`.
*   If `x % i == 1`, add `i` to the `newNumbers` set.
*   After checking all numbers on the board, add all numbers from `newNumbers` to the main `board` set.
*   If the size of the `board` set did not change in an iteration, the state has stabilized, and we can break the loop early.
*   Finally, return the size of the `board` set.

## Optimized Simulation using BFS
Instead of simulating day-by-day, we can reframe the problem as finding all reachable nodes in a graph starting from node `n`. A number `i` is reachable from `x` if `x % i == 1`. This can be efficiently solved using a Breadth-First Search (BFS) algorithm. We use a queue to keep track of numbers we need to process and a set to store the numbers we've already found (and visited).
**Time:** O(n^2). Each number from 1 to `n` is enqueued and processed at most once. Processing a number involves a loop from 1 to `n`. · **Space:** O(n) for the `HashSet` and the `Queue`. In the worst case, most numbers from 1 to `n` could be added.
**Pros:** Much more efficient than the direct simulation.; Avoids redundant computations by processing each number only once.
**Cons:** While more efficient than brute-force, it is still not optimal.; It performs unnecessary computations compared to the mathematical solution.
### Explanation
This approach treats the problem as a graph traversal. The numbers from 1 to `n` are the nodes. A directed edge exists from `x` to `i` if `i` can be generated from `x`. We start our traversal from `n`. We use a queue to implement BFS and a set to keep track of visited nodes (the numbers on the board). Initially, `n` is added to both the queue and the set. We then repeatedly extract a number `x` from the queue, find all new numbers `i` it can generate (`x % i == 1`), and for any `i` that hasn't been visited yet, we add it to the set and the queue. This process continues until the queue is empty, at which point we have found all distinct numbers that can ever appear on the board. The final answer is the size of the set.

```java
import java.util.HashSet;
import java.util.Set;
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int distinctIntegers(int n) {
        Set<Integer> board = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        board.add(n);
        queue.add(n);

        while (!queue.isEmpty()) {
            int x = queue.poll();
            for (int i = 1; i <= n; i++) {
                if (x % i == 1) {
                    // .add() returns true if the element was new to the set
                    if (board.add(i)) { 
                        queue.add(i);
                    }
                }
            }
        }
        return board.size();
    }
}
```
### Algorithm
*   Initialize a `HashSet<Integer>` `board` to store the results and act as a visited set.
*   Initialize a `Queue<Integer>` `queue` to manage the numbers to be processed.
*   Add the starting number `n` to both the `board` and the `queue`.
*   While the `queue` is not empty:
    *   Dequeue a number `x`.
    *   Iterate `i` from 1 to `n`.
    *   If `x % i == 1` and `i` is not yet on the `board`:
        *   Add `i` to the `board` set.
        *   Enqueue `i` for future processing.
*   When the `queue` is empty, all reachable numbers have been found. Return the size of the `board` set.

## Constant Time Mathematical Approach
The most efficient approach comes from a mathematical observation of the problem's rules. By analyzing the condition `x % i == 1`, we can deduce a pattern that reveals the final state of the board without any simulation. The large number of days (`10^9`) is a strong hint that the system reaches a predictable fixed point quickly.
**Time:** O(1), as it only involves a single conditional check. · **Space:** O(1), as no extra space is required.
**Pros:** Extremely efficient with constant time and space complexity.; Provides a complete solution by understanding the problem's core mechanics.; Simple and elegant implementation.
**Cons:** Requires a logical deduction and mathematical insight rather than direct implementation of the problem statement.
### Explanation
Let's analyze the core rule: a number `i` is placed on the board if `x % i == 1` for some `x` already on the board. This is only possible if `i > 1`.

Case 1: `n > 2`
*   Initially, `n` is on the board. Let's check if `n-1` can be added. We test `x=n` and `i=n-1`. The condition is `n % (n-1) == 1`, which is true. Since `n > 2`, we have `n-1 >= 2`, so `i=n-1` is a valid number to be placed on the board.
*   Now, `n-1` is on the board. If `n-1 > 2` (i.e., `n > 3`), we can similarly show that `n-2` will be added.
*   This establishes a chain reaction: `n` causes `n-1` to be added, which causes `n-2` to be added, and so on, all the way down to `3` causing `2` to be added.
*   Once `2` is on the board, it cannot add any new numbers, because `2 % i == 1` requires `i` to be a divisor of `2-1=1`, and no such `i > 1` exists.
*   Therefore, for any `n > 2`, the board will eventually contain all integers from `2` to `n`. The total count of these numbers is `n - 2 + 1 = n-1`.

Case 2: `n <= 2`
*   If `n=1` or `n=2`, the chain reaction described above never starts. No number `i > 1` satisfies `n % i == 1`. Thus, the board only ever contains the initial number. The count is 1.

This leads to a very simple O(1) solution.

```java
class Solution {
    public int distinctIntegers(int n) {
        // If n is 1 or 2, no new numbers can be added.
        // For n=1, 1%i==1 is impossible.
        // For n=2, 2%i==1 requires i to be a divisor of 1, so i=1, but we need i>1.
        if (n <= 2) {
            return 1;
        }
        // If n > 2, n-1 is added, which adds n-2, ..., until 2 is added.
        // The final set of numbers is {2, 3, ..., n}.
        // The size of this set is n-1.
        return n - 1;
    }
}
```
### Algorithm
*   Analyze the condition `x % i == 1`. This implies `i` is a divisor of `x - 1` and `i > 1`.
*   If `n > 2`, then `n-1` is a valid choice for `i` since `n % (n-1) == 1` and `2 <= n-1 <= n`. Thus, `n-1` is added to the board.
*   If a number `k >= 3` is on the board, `k-1` will be added because `k % (k-1) == 1`.
*   This creates a chain reaction: `n` places `n-1`, `n-1` places `n-2`, ..., `3` places `2`.
*   The chain stops at `2`, as `2-1=1` has no divisors greater than 1.
*   So for `n > 2`, all numbers from `2` to `n` will eventually be on the board. The count is `n-1`.
*   For `n=1` or `n=2`, this chain reaction does not start. The board will only contain the initial number. The count is 1.
*   The final logic is: if `n <= 2`, return 1; otherwise, return `n-1`.

# Solutions
### Java

```java
class Solution {
public
  int distinctIntegers(int n) { return Math.max(1, n - 1); }
}

```

### CPP

```cpp
class Solution {
public:
  int distinctIntegers(int n) { return max(1, n - 1); }
};

```

### Python

```python
class Solution:
    def distinctIntegers(self, n: int) -> int: return max(1, n - 1)

```