Get started

Count Distinct Numbers on Board — Easy Problem & Solution

You write n on a board. Every day, for each number x already on the board, you add every y in [1, n] such that x % y == 1. Numbers never repeat on the board.

  • Difficulty: Easy
  • Topics: Math, Simulation, Number Theory
  • Asked at: Amazon, TCS, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You write n on a board. Every day, for each number x already on the board, you add every y in [1, n] such that x % y == 1. Numbers never repeat on the board.

Return how many distinct numbers the board holds after 10^9 days.

Example 1

Input: n = 5
Output: 4
Explanation: 5 % 4 = 1 adds 4; then 4 % 3 = 1 adds 3; then 3 % 2 = 1 adds 2. The board ends as {2,3,4,5}.

Example 2

Input: n = 3
Output: 2
Explanation: 3 % 2 = 1 adds 2, and 2 adds nothing new.

Example 3

Input: n = 1
Output: 1
Explanation: 1 % y == 1 has no solution in range, so only 1 stays.

Constraints

  • 1 <= n <= 100

How to solve Count Distinct Numbers on Board

For any x > 2, x % (x - 1) == 1, so writing x immediately makes x - 1 appear. Starting from n, the cascade sweeps all the way down to 2, and 1 is unreachable because y would have to exceed x.

Approach

  1. Handle n == 1 separately: the board is just {1}, so the answer is 1.
  2. Otherwise the board becomes {2, 3, …, n}, which has n - 1 numbers.

Why it works

By induction every x in [3, n] adds x - 1, so all of 2 … n appear. And 1 never does: x % y == 1 requires y > 1 and x > y, so the value added is always at least 2. Nothing outside [1, n] is ever considered.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • Actually simulating 10^9 days is a trap — the board stabilises within n steps.
  • n = 1 is the only case where the answer is not n - 1.

Reference solution

Python

def distinctIntegers(n: int) -> int:
    return 1 if n == 1 else n - 1

JavaScript

var distinctIntegers = function(n) {
    return n === 1 ? 1 : n - 1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue