跳转至

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

题目描述

给你一个正整数 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

解法

方法一：脑筋急转弯

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

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

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

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

1
2
3
4
5
class Solution {
    public int distinctIntegers(int n) {
        return Math.max(1, n - 1);
    }
}

1
2
3
4
5
6
class Solution {
public:
    int distinctIntegers(int n) {
        return max(1, n - 1);
    }
};

1
2
3
func distinctIntegers(n int) int {
    return max(1, n-1)
}

1
2
3
function distinctIntegers(n: number): number {
    return Math.max(1, n - 1);
}

1
2
3
4
5
impl Solution {
    pub fn distinct_integers(n: i32) -> i32 {
        (1).max(n - 1)
    }
}

评论