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

1
2
3
4
5
6

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

1
2
3
4
5

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

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

Code

1
2
3
4
5
6

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

func distinctIntegers(n int) int {
    if n == 1 { return 1 }
    return n - 1
}
1
2
3
4
5

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

class Solution {
    fun distinctIntegers(n: Int): Int {
        return if (n == 1) 1 else n - 1
    }
}
1
2
3

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

impl Solution {
    pub fn distinct_integers(n: i32) -> i32 {
        if n == 1 { 1 } else { n - 1 }
    }
}
1
2
3
4
5

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

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.