Easy
题目描述
给你一个正整数 n，它最初被放在板上。每一天，在连续 10^9 天内，你都要执行以下过程：
- 对于板上存在的每个数字
x，找到所有满足1 <= i <= n且x % i == 1的数字i。 - 然后，将这些数字放在板上。
返回在 10^9 天过去后，板上存在的不同整数的数量。
注意：
- 一旦数字被放在板上，它将一直保留到最后。
%表示取模运算。例如，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
提示：
- 对于
n > 2，n % (n - 1) == 1，因此n - 1将在第二天被添加到板上。 - 由于操作进行了很长时间，所有小于
n的数字（除了 1）都会被添加到板上。 - 如果
n == 1会发生什么？
解题思路
这道题的关键在于观察数学规律。我们需要分析当 x % i == 1 时，哪些数字会被添加到板上。
核心观察：
- 当
x % i == 1时，意味着x = k*i + 1，其中k是正整数 - 对于任何数字
x > 1，都有x % (x-1) == 1，因为x = 1*(x-1) + 1 - 这意味着如果板上有数字
x，那么x-1也会被添加到板上（除非x-1 = 1）
模拟过程分析：
- 从
n开始，n % (n-1) == 1，所以n-1会被添加 - 然后
(n-1) % (n-2) == 1，所以n-2会被添加 - 这个过程会一直持续到 2
特殊情况：
- 当
n = 1时，没有满足条件的i（因为要求1 <= i <= n且i要使得1 % i == 1，但1 % 1 = 0） - 当
n > 1时，最终板上会有从 2 到n的所有整数
因此答案很简单：
- 如果
n = 1，返回 1 - 如果
n > 1，返回n - 1
这是因为经过足够长时间后，除了 1 以外的所有小于等于 n 的数字都会出现在板上。
代码实现
class Solution {
public:
int distinctIntegers(int n) {
return n == 1 ? 1 : n - 1;
}
};
class Solution:
def distinctIntegers(self, n: int) -> int:
return 1 if n == 1 else n - 1
public class Solution {
public int DistinctIntegers(int n) {
return n == 1 ? 1 : n - 1;
}
}
var distinctIntegers = function(n) {
if (n === 1) return 1;
return n - 1;
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(1) |
| 空间复杂度 | O(1) |