LeetCode 3718 - Smallest Missing Multiple of K

The problem asks us to find the smallest positive multiple of k that is not present in a given integer array nums. In other words, if we consider the infinite sequence of numbers k, 2k, 3k, 4k…, we need to identify the first number in this sequence that does not appear in nums.

leetcodeeasyarrayhash-table

LeetCode Problem 3718

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to find the smallest positive multiple of k that is not present in a given integer array nums. In other words, if we consider the infinite sequence of numbers k, 2k, 3k, 4k…, we need to identify the first number in this sequence that does not appear in nums. The input consists of an integer array nums of size between 1 and 100 and an integer k ranging from 1 to 100. Each element in nums is between 1 and 100. The expected output is a single integer representing the smallest missing multiple of k.

The constraints suggest that the array and number sizes are small, so an approach that involves scanning numbers sequentially is acceptable. Edge cases include arrays that do not contain any multiples of k, arrays that contain all multiples of k up to a certain point, or k = 1 which means every positive integer is a multiple.

Approaches

The brute-force approach would iterate through multiples of k starting from k itself and check whether each multiple exists in nums. We continue this process until we find a multiple that is not in the array. This works correctly, but if nums were larger, the repeated membership checking could become inefficient. A key improvement is to use a hash set to store nums, allowing O(1) lookup time for each multiple.

The insight is that since the maximum possible number in nums is 100, and k is also at most 100, the smallest missing multiple will not be unreasonably large, so iterating multiples of k is efficient. Using a set ensures constant-time checks and makes the solution optimal in both clarity and performance.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Iterate multiples of k and scan nums each time; n is length of nums, m is number of multiples until missing one is found
Optimal O(n) O(n) Store nums in a set, then iterate multiples of k until a missing one is found

Algorithm Walkthrough

  1. Initialize a hash set containing all elements of nums. This allows us to check membership in constant time.
  2. Initialize a variable multiple to k, representing the current multiple of k we are checking.
  3. Enter a loop: while multiple exists in the set, increment multiple by k. This continues checking the next multiple of k until one is missing.
  4. Once a multiple is not found in the set, return that multiple as the result.

Why it works: Every positive multiple of k is checked sequentially starting from the smallest. The set guarantees that lookup is efficient. Since we increment by k each time, we never miss a potential multiple. The first multiple not in nums is returned as required.

Python Solution

from typing import List

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        nums_set = set(nums)
        multiple = k
        while multiple in nums_set:
            multiple += k
        return multiple

In the implementation, we first convert nums to a set to allow O(1) membership checks. We then start with the first multiple of k and check if it exists in the set. If it does, we increment by k and check again. This continues until we find a missing multiple, which is then returned. This matches the algorithm walkthrough directly.

Go Solution

func missingMultiple(nums []int, k int) int {
    numsSet := make(map[int]struct{})
    for _, num := range nums {
        numsSet[num] = struct{}{}
    }
    
    multiple := k
    for {
        if _, exists := numsSet[multiple]; !exists {
            return multiple
        }
        multiple += k
    }
}

The Go solution uses a map to simulate a set. We iterate through nums and store each element as a key in the map. Then, starting from k, we check each multiple in the map. If it does not exist, we return it. Go requires a more explicit map lookup and use of empty structs to minimize memory usage compared to Python's built-in set.

Worked Examples

Example 1: nums = [8, 2, 3, 4, 6], k = 2

Step multiple multiple in nums_set? Action
1 2 Yes multiple += 2 → 4
2 4 Yes multiple += 2 → 6
3 6 Yes multiple += 2 → 8
4 8 Yes multiple += 2 → 10
5 10 No return 10

Example 2: nums = [1, 4, 7, 10, 15], k = 5

Step multiple multiple in nums_set? Action
1 5 No return 5

Complexity Analysis

Measure Complexity Explanation
Time O(n) Converting nums to a set is O(n), iterating multiples is bounded by n since numbers are ≤ 100
Space O(n) Storing nums in a set requires O(n) space

The solution is efficient because it leverages constant-time lookups and the small constraints of the problem guarantee that we do not check excessively many multiples.

Test Cases

# Provided examples
assert Solution().missingMultiple([8,2,3,4,6], 2) == 10  # first missing multiple of 2
assert Solution().missingMultiple([1,4,7,10,15], 5) == 5  # first missing multiple of 5

# Edge cases
assert Solution().missingMultiple([1,2,3,4,5], 1) == 6  # k = 1, missing first positive integer
assert Solution().missingMultiple([100], 50) == 50  # missing multiple smaller than array element
assert Solution().missingMultiple([10,20,30,40], 10) == 50  # all multiples up to 40 present

# Minimal input
assert Solution().missingMultiple([1], 2) == 2  # only 1 in array, k=2
Test Why
[8,2,3,4,6], 2 Checks standard case where missing multiple is beyond largest in array
[1,4,7,10,15], 5 Checks missing multiple smaller than some numbers in array
[1,2,3,4,5], 1 Edge case with k = 1
[100], 50 Checks missing multiple smaller than array value
[10,20,30,40], 10 All multiples present up to a point
[1], 2 Minimal array size

Edge Cases

One important edge case is when k = 1. Since every positive integer is a multiple of 1, the missing multiple is simply the first positive integer not in nums. Our implementation correctly handles this by checking sequentially starting from 1.

Another edge case occurs when all multiples of k up to the largest number in nums are present. For instance, nums = [10,20,30] and k = 10. The algorithm correctly identifies the next multiple after the largest, which is 40, as missing.

A third edge case is when nums contains numbers unrelated to k, such as nums = [3,7,11] and k = 5. The smallest missing multiple is 5, which our set-based lookup ensures is returned immediately without unnecessary iteration.

These edge cases validate that the solution is robust, handles minimal and maximal scenarios, and correctly returns the smallest missing multiple in all situations.