Count distinct numbers on board

Array Hash Table Math Simulation

61.7% acceptance

Feb 25, 2026

319

292

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

Solution

Rust

Time O(1)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn distinct_integers(n: i32) -> i32 {
    // For n == 1: only {1} on board, never changes. Answer = 1.
    // For n >= 2: all numbers from 2 to n will eventually appear. Answer = n - 1.
    // (Number 1 never appears since x % i = 1 requires i | (x-1), and i >= 2 would
    //  need x-1 >= 2 meaning x >= 3, but we'd need i=1 giving x%1=0, not 1.)
    if n == 1 { 1 } else { n - 1 }
  }
}