Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Build confidence with an intuition-first walkthrough focused on array fundamentals.
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 <= 100Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Math
5
3
count-of-matches-in-tournament)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2549: Count Distinct Numbers on Board
class Solution {
public int distinctIntegers(int n) {
return Math.max(1, n - 1);
}
}
// Accepted solution for LeetCode #2549: Count Distinct Numbers on Board
func distinctIntegers(n int) int {
return max(1, n-1)
}
# Accepted solution for LeetCode #2549: Count Distinct Numbers on Board
class Solution:
def distinctIntegers(self, n: int) -> int:
return max(1, n - 1)
// Accepted solution for LeetCode #2549: Count Distinct Numbers on Board
impl Solution {
pub fn distinct_integers(n: i32) -> i32 {
(1).max(n - 1)
}
}
// Accepted solution for LeetCode #2549: Count Distinct Numbers on Board
function distinctIntegers(n: number): number {
return Math.max(1, n - 1);
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.