2549. Count Distinct Numbers on Board LeetCode Solution
In this guide, you will get 2549. Count Distinct Numbers on Board LeetCode Solution with the best time and space complexity. The solution to Count Distinct Numbers on Board problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Distinct Numbers on Board
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 of distinct 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.
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.
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
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(1)
2549. Count Distinct Numbers on Board LeetCode Solution in C++
class Solution {
public:
int distinctIntegers(int n) {
return max(n - 1, 1);
}
}; /* code provided by PROGIEZ */
2549. Count Distinct Numbers on Board LeetCode Solution in Java
class Solution {
public int distinctIntegers(int n) {
return Math.max(n - 1, 1);
}
} // code provided by PROGIEZ
2549. Count Distinct Numbers on Board LeetCode Solution in Python
class Solution:
def distinctIntegers(self, n: int) -> int:
return max(n - 1, 1) # code by PROGIEZ
