3718. Smallest Missing Multiple of K

Intuition

Walk the multiples of k in increasing order and return the first one that isn't present. A hash set makes each membership test O(1).

The scan is guaranteed to end quickly: every value in nums is at most 100, so the first multiple exceeding 100 cannot possibly be in the array. At worst that's k, 2k, ..., up to just past 100, about 100 / k + 1 checks.

Approach

1. Build a set from nums.
2. Starting at m = k, increment by k while m is in the set.
3. Return the first m not in the set.

Complexity

• Time: O(n + 100/k), building the set dominates
• Space: O(n), the membership set

Edge Cases

• k itself missing → answer is k immediately (Example 2)
• k > 100 → k can never appear in nums, so the answer is k
• Every multiple up to 100 present (e.g. k = 1 with nums covering 1..100) → answer is 101
• Values in nums that aren't multiples of k are simply irrelevant
• The answer can exceed the largest value in nums, so a fixed-size lookup must be bounds-checked

from typing import List


class Solution:
    def smallestMissingMultiple(self, nums: List[int], k: int) -> int:
        """
        3718. Smallest Missing Multiple of K
        Time: O(n)
        Space: O(n)
        """
        present = set(nums)
        m = k
        while m in present:
            m += k
        return m

/**
 * 3718. Smallest Missing Multiple of K
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int smallestMissingMultiple(int[] nums, int k) {
        boolean[] present = new boolean[101]; // values are in [1, 100]
        for (int x : nums) {
            present[x] = true;
        }

        int m = k;
        // a multiple above 100 can never appear in nums, so bounds-check first
        while (m <= 100 && present[m]) {
            m += k;
        }
        return m;
    }
}