What is the easiest way to track numbers for Count Distinct Numbers on Board?

Use a hash set to store numbers as they are generated and check for new additions each iteration.

Do I need to simulate a billion days literally?

No, recognizing that n % (n - 1) == 1 allows the board to reach all numbers down to 2 quickly without full simulation.

Can this problem be solved without hash sets?

Yes, but using a hash set prevents duplicates and directly captures the array scanning plus hash lookup pattern efficiently.

What is the expected time complexity?

O(n) in practice since the board can only grow up to n - 1 distinct numbers and each number is processed once.

Does the solution change for small n values like 1 or 2?

Yes, for n = 1 or 2, the board quickly stabilizes with fewer distinct numbers, but the pattern and hash tracking approach remains the same.

#2549

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计桌面上的不同数字

给你一个正整数 n ，开始时，它放在桌面上。在 10 9 天内，每天都要执行下述步骤：对于出现在桌面上的每个数字 x ，找出符合 1 且满足 x % i == 1 的所有数字 i 。然后，将这些数字放在桌面上。返回在 10 9 天之后，出现在桌面上的不同整数的数目。注意：一旦数字放在桌…

数组哈希表数学模拟

题目描述

给你一个正整数 n ，开始时，它放在桌面上。在 10⁹ 天内，每天都要执行下述步骤：

对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
然后，将这些数字放在桌面上。

返回在 10⁹ 天之后，出现在桌面上的不同整数的数目。

注意：

一旦数字放在桌面上，则会一直保留直到结束。
% 表示取余运算。例如，14 % 3 等于 2 。

示例 1：

输入：n = 5
输出：4
解释：最开始，5 在桌面上。 
第二天，2 和 4 也出现在桌面上，因为 5 % 2 == 1 且 5 % 4 == 1 。 
再过一天 3 也出现在桌面上，因为 4 % 3 == 1 。 
在十亿天结束时，桌面上的不同数字有 2 、3 、4 、5 。

示例 2：

输入：n = 3 
输出：2
解释： 
因为 3 % 2 == 1 ，2 也出现在桌面上。 
在十亿天结束时，桌面上的不同数字只有两个：2 和 3 。

提示：

1 <= n <= 100

lightbulb

解题思路

方法一：脑筋急转弯

由于每一次对桌面上的数字 $n$ 进行操作，会使得数字 $n-1$ 也出现在桌面上，因此最终桌面上的数字为 $[2,...n]$ ，共 $n-1$ 个数字。

注意到 $n$ 可能为 $1$ ，因此需要特判。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

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

speed

复杂度分析

指标	值
时间	complexity depends on n since the simulation can add up to n - 1 numbers. Space complexity is O(n) for the hash set storing distinct numbers.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for recognition of the n % (n - 1) pattern to shortcut iterations.
question_mark
Expect discussion on hash set usage to track distinct numbers efficiently.
question_mark
Candidate may suggest stopping simulation when no new numbers appear, showing understanding of growth limits.

warning

常见陷阱

外企场景

error
Attempting to simulate a billion days literally rather than leveraging patterns.
error
Forgetting to check if modulo results are already in the board set, causing duplicates.
error
Miscounting initial number n or neglecting small numbers like 2 and 1 if n is small.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute distinct numbers for a board starting with multiple initial integers.
arrow_right_alt
Return the sorted list of distinct numbers instead of just the count.
arrow_right_alt
Change the modulo operation to a different arithmetic function and compute distinct results.

help

常见问题

外企场景

继续练习

#2521 数组乘积中的不同质因数数目 #2584 分割数组使乘积互质 #2593 标记所有元素后数组的分数