tatic/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:Tcd3,

Problem

You are given a positive integer n, that is initially placed on a board. Every day, for 109 days, you perform the following procedure:

For each number x present on the board, find all numbers 1 <= i <= n such that x % i == 1.
Then, place those numbers on the board.

Return the number ofdistinct integers present on the board after 109 days have elapsed.

Note:

Once a number is placed on the board, it will remain on it until the end.
% stands for the modulo operation. For example, 14 % 3 is 2.

Examples

Example 1

Input: n = 5
Output: 4
Explanation: Initially, 5 is present on the board. 
The next day, 2 and 4 will be added since 5 % 2 == 1 and 5 % 4 == 1. 
After that day, 3 will be added to the board because 4 % 3 == 1. 
At the end of a billion days, the distinct numbers on the board will be 2, 3, 4, and 5.

Example 2

Input: n = 3
Output: 2
Explanation: 
Since 3 % 2 == 1, 2 will be added to the board. 
After a billion days, the only two distinct numbers on the board are 2 and 3.

Constraints

1 <= n <= 100

Solution

Method 1 – Mathematical Observation

Intuition

Every number from 1 to n can be generated except 1 (if n > 1). This is because for any x > 1, x % (x-1) == 1, so (x-1) will be added, and this process continues until 1. But 1 % i == 1 only for i = 2, so 1 is only added if n = 1. Thus, for n > 1, all numbers from 2 to n will be present.

Approach

If n == 1, return 1.
Otherwise, return n - 1 (all numbers from 2 to n).

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int distinctIntegers(int n) {\n        return n == 1 ? 1 : n - 1;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func distinctIntegers(n int) int {\n    if n == 1 { return 1 }\n    return n - 1\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int distinctIntegers(int n) {\n        return n == 1 ? 1 : n - 1;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun distinctIntegers(n: Int): Int {\n        return if (n == 1) 1 else n - 1\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def distinctIntegers(self, n: int) -> int:\n        return 1 if n == 1 else n - 1","lang":"python"},{"language":"Rust","code":"impl Solution {\n    pub fn distinct_integers(n: i32) -> i32 {\n        if n == 1 { 1 } else { n - 1 }\n    }\n}","lang":"rust"},{"language":"TypeScript","code":"class Solution {\n    distinctIntegers(n: number): number {\n        return n === 1 ? 1 : n - 1;\n    }\n}","lang":"typescript"}]

Complexity

⏰ Time complexity: O(1), as the answer is computed in constant time.
🧺 Space complexity: O(1), only a constant amount of space is used.

8:["$","div",null,{"className":"max-w-7xl mx-auto px-4 py-8","children":[["$","header",null,{"className":"mb-8 pb-4","c

Related Tags