409. Smallest Missing Multiple of K

Drop nums into a hash set for O(1) membership, then walk the multiples of k in order — k, 2k, 3k, ... — and return the first one that isn't in the set.

Idea

The multiples of k are k, 2k, 3k, ..., an infinite increasing sequence. We want the smallest one that does not appear in nums. Two facts make this simple:

1. Membership testing is the core operation, so we put every value of nums into a hash set for O(1) lookups.
2. Because we generate the multiples in increasing order, the first multiple we find missing from the set is automatically the smallest.

Walk-through

Take nums = [8, 2, 3, 4, 6], k = 2.

1. Build the set seen = {8, 2, 3, 4, 6}.
2. Start at the first multiple m = 2. Is 2 in seen? Yes → it's present, advance to the next multiple.
3. m = 4. In seen? Yes → advance.
4. m = 6. In seen? Yes → advance.
5. m = 8. In seen? Yes → advance.
6. m = 10. In seen? No → 10 is the smallest multiple of 2 missing from nums. Return 10.

Why it terminates

nums holds at most n values, so at most n of the multiples k, 2k, ... can be present. Within the first n + 1 multiples we are guaranteed to hit one that is missing, so the loop always stops.

Complexity

• Time: O(n) — building the set is O(n), and we test at most n + 1 multiples, each in O(1).
• Space: O(n) — the hash set stores up to n values.

class Solution {
    public int missingMultiple(int[] nums, int k) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) seen.add(num);
        int m = k;
        while (seen.contains(m)) m += k;
        return m;
    }
}