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

本文主要是介绍【Leetcode】2549. 统计桌面上的不同数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

题目链接🔗
给你一个正整数 $n$ ，开始时，它放在桌面上。在 $10^9$ 天内，每天都要执行下述步骤：

• 对于出现在桌面上的每个数字 x ，找出符合 $1\le i\le 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\le n\le 100$

思路

• 第一天，桌面上只有一个数字$n$，我们可以选择$i=n-1$，因为$n\%(n-1)=1$
• 第二天，桌面上有两个数字$n$、$n-1$，我们可以选择$i=n-2$，因为$(n-1)\%(n-2)=1$
• ···
• 第$n-2$天，桌面上有$n-2$个数字$n$、$n-1$、$\cdot \cdot \cdot$、$3$，我们可以选择$i=2$，因为$3\%2=1$
• 第$n-1$天，桌面上有$n-1$个数字$n$、$n-1$、$\cdot \cdot \cdot$、$2$，此时已经无法添加任何数字

·注意一开始就是$n=1$的话，桌面就会出现$1$，总共一个数字；否则桌面上不会出现$1$，总计$n-1$个数字

代码

class Solution {
public:int distinctIntegers(int n) {return max(1,n-1);}
};

复杂度分析

时间复杂度

O(1)

空间复杂度

O(1)

结果

总结

数学结论题

这篇关于【Leetcode】2549. 统计桌面上的不同数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---