You are given an integer array nums and an integer k. Your task is to find the smallest positive multiple of k that does not appear in nums.

A multiple of k is any positive integer that is divisible by k. In other words, the multiples of k are k * 1, k * 2, k * 3, and so on.

For example, if nums = [2, 4, 8] and k = 2:

• The multiples of 2 in order are: 2, 4, 6, 8, ...
• 2 is in the array, 4 is in the array, but 6 is not.
• Therefore, the answer is 6.

The goal is to check the multiples of k one by one, starting from the smallest (k * 1), and return the first one that is missing from the array.

The problem asks for the smallest missing positive multiple of k, which naturally suggests a simple strategy: check the multiples of k one by one in increasing order — k * 1, k * 2, k * 3, ... — and stop as soon as we find one that is not in nums. Since we check them from smallest to largest, the first missing one we encounter is guaranteed to be the answer.

The only remaining concern is efficiency. For each multiple, we need to ask: "does this value exist in nums?" If we scan the entire array every time, each check costs O(n). Instead, we can put all elements of nums into a hash set first. A hash set answers membership queries in O(1) on average, so every check becomes instant.

We also know this process must terminate quickly. The array has only n elements, so it can contain at most n distinct multiples of k. That means by the time we reach the multiple k * (n + 1), at least one of the first n + 1 multiples must be missing. Therefore, the enumeration runs at most n + 1 rounds, giving an overall linear-time solution.

We use a hash table (set) combined with enumeration, following these steps:

Step 1: Build a hash set from the array

We first store all the numbers from nums into a set s:

s = set(nums)

This is the key data structure choice. Converting the array into a set takes O(n) time once, and afterwards each membership check x in s runs in O(1) on average — far better than scanning the array repeatedly.

Step 2: Enumerate multiples of k in increasing order

Starting from i = 1, we generate each positive multiple x = k * i in sequence:

for i in count(1):
    x = k * i

Here count(1) from the itertools module produces the infinite sequence 1, 2, 3, ..., so x takes the values k, 2k, 3k, ... in order.

Step 3: Return the first missing multiple

For each multiple x, we check whether it exists in the set. The moment we find one that is absent, we return it immediately:

if x not in s:
    return x

Because we enumerate multiples from smallest to largest, the first absent multiple is guaranteed to be the smallest missing one — exactly what the problem asks for.

Complete Code

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        s = set(nums)
        for i in count(1):
            x = k * i
            if x not in s:
                return x

Complexity Analysis

• Time Complexity: O(n), where n is the length of nums. Building the set costs O(n). Since nums contains at most n distinct multiples of k, the loop runs at most n + 1 iterations, each with an O(1) set lookup.
• Space Complexity: O(n), used by the hash set storing the elements of nums.