Welcome to Subscribe On Youtube

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

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}$.

  • 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;
            }
        }
    }
}


  • 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;
            }
        }
    }
};


  • 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


  • 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
		}
	}
}


  • 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;
        }
    }
}

All Problems

All Solutions