Skip to content

3718. Smallest Missing Multiple of K

Description

Given an integer array nums and an integer k, return the smallest positive multiple of k that is missing from nums.

A multiple of k is any positive integer divisible by k.

 

Example 1:

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

Output: 10

Explanation:

The multiples of k = 2 are 2, 4, 6, 8, 10, 12... and the smallest multiple missing from nums is 10.

Example 2:

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

Output: 5

Explanation:

The multiples of k = 5 are 5, 10, 15, 20... and the smallest multiple missing from nums is 5.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100

Solutions

Solution 1: Hash Table + Enumeration

Thinking

We need the smallest positive multiple \(k,2k,\ldots\) that is absent. Both \(n\) and \(k\) are at most \(100\), so a set of the array plus an increasing scan of multiples suffices.

We first use a hash table \(\textit{s}\) to store the numbers that appear in the array \(\textit{nums}\). Then, starting from the first positive multiple of \(k\), which is \(k \times 1\), we enumerate each positive multiple in sequence until we find the first multiple that does not appear in the hash table \(\textit{s}\), which is the answer.

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
7
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int missingMultiple(int[] nums, int k) {
        boolean[] s = new boolean[101];
        for (int x : nums) {
            s[x] = true;
        }
        for (int i = 1;; ++i) {
            int x = k * i;
            if (x >= s.length || !s[x]) {
                return x;
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int missingMultiple(vector<int>& nums, int k) {
        unordered_set<int> s;
        for (int x : nums) {
            s.insert(x);
        }
        for (int i = 1;; ++i) {
            int x = k * i;
            if (!s.contains(x)) {
                return x;
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func missingMultiple(nums []int, k int) int {
    s := map[int]bool{}
    for _, x := range nums {
        s[x] = true
    }
    for i := 1; ; i++ {
        if x := k * i; !s[x] {
            return x
        }
    }
}

1
2
3
4
5
6
7
8
9
function missingMultiple(nums: number[], k: number): number {
    const s = new Set<number>(nums);
    for (let i = 1; ; ++i) {
        const x = k * i;
        if (!s.has(x)) {
            return x;
        }
    }
}

Comments