2549.统计桌面上的不同数字

【LetMeFly】2549.统计桌面上的不同数字：数学O(1) / 模拟O(n^3)

力扣题目链接：https://leetcode.cn/problems/count-distinct-numbers-on-board/

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

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

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

注意：

• 一旦数字放在桌面上，则会一直保留直到结束。
• % 表示取余运算。例如，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

方法一：模拟

每次用$i$从$1$枚举到$n-1$：

每次用$j$从$1$枚举到$n$：

如果$j\mod i == 1$并且$i$还没有在桌面上，就把$i$放到桌面上。

直到本次枚举没有新数字被放到桌面上。

• 时间复杂度$O(n^3)$，最多可能枚举$n$轮
• 空间复杂度$O(n)$

方法二：数学

对于$x\geq2$，一定有$x\mod (x-1)=1$。

如果操作足够都次，$n$、$n-1$、$n-2$、$\cdots$、$2$一定会全部出现在桌子上。

不难发现$n\leq 100$而枚举次数为$10^9$，每次枚举至少出现一个新数字，因此$10^9$足够$2$到$n$的所有数字出现在桌子上。

• 时间复杂度$O(1)$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int distinctIntegers(int n) {
        return n == 1 ? 1 : n - 1;
    }
};

Python

class Solution:
    def distinctIntegers(self, n: int) -> int:
        return 1 if n == 1 else n - 1

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/136963667