Difficulty: Easy | Acceptance: 61.70% | Paid: No Topics: Array, Hash Table, Math, Simulation
You are given a positive integer n, that is initially placed on a board. You will perform the following operation exactly n - 1 times:
- If the number x on the board is greater than 1, replace it with x - 1.
Return the number of distinct numbers that will be on the board after performing all operations.
- Examples
- Constraints
- Approach 1: Simulation with Set
- Approach 2: Mathematical Formula
Examples
Example 1:
Input: n = 5
Output: 5
Example 2:
Input: n = 0
Output: 1
Constraints
0 <= n <= 10⁵
Approach 1: Simulation with Set
Intuition Simulate the process by iterating from n down to 1 and collecting all numbers in a set to count distinct values.
Steps
- Initialize an empty set to store distinct numbers
- Iterate from n down to 1
- Add each number to the set
- Return the size of the set
python
class Solution:
def distinctIntegers(self, n: int) -> int:
distinct = set()
for i in range(n, 0, -1):
distinct.add(i)
return len(distinct)
Complexity
- Time: O(n)
- Space: O(n)
- Notes: Uses extra space for the set but clearly demonstrates the simulation process
Approach 2: Mathematical Formula
Intuition Observe that the process generates all integers from 1 to n, so the answer is simply max(1, n).
Steps
- Return max(1, n) directly
python
class Solution:
def distinctIntegers(self, n: int) -> int:
return max(1, n)
Complexity
- Time: O(1)
- Space: O(1)
- Notes: Optimal solution with constant time and space complexity