Watch 10 video solutions for Count Distinct Numbers on Board, a easy level problem involving Array, Hash Table, Math. This walkthrough by NeetCodeIO has 14,668 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a positive integer n, that is initially placed on a board. Every day, for 109 days, you perform the following procedure:
x present on the board, find all numbers 1 <= i <= n such that x % i == 1.Return the number of distinct integers present on the board after 109 days have elapsed.
Note:
% 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.
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