Smallest Missing Multiple of K
Asked at Microsoft
Problem
Given an integer array nums and an integer k, find the smallest positive multiple of k that is not present in the array. Return this value.
Asked At
| Company | Difficulty | |
|---|---|---|
| Microsoft | EASY | View all Microsoft questions → |
How to Think About It
Brute force: check k, 2k, 3k, ... in order and return the first multiple not in nums.
Convert nums to a set for O(1) lookups and iterate through multiples of k.
Sort the array first and use binary search for each candidate multiple.
Optimal: use a hash set and enumerate multiples of k starting from k itself until one is missing.
If the array contains all multiples of k in a range, the answer is the next multiple beyond the max element.
Optimal Approach
Insert all elements of nums into a hash set. Start checking multiples of k beginning with k itself: k, 2k, 3k, ... For each multiple, check if it exists in the set. The first multiple not found is the answer. The search terminates quickly because the answer is at most len(nums) + 1 multiplied by k.
What Trips People Up in Real Interviews
Clarify whether k itself could be missing from the array.
Handle edge case where k is 0 — discuss assumptions with interviewer.
The set approach is simplest and runs in O(n + m/k) time where m is the answer.
Do not confuse with finding the smallest missing positive integer overall.
Confirm that all multiples checked must be positive.
Solution Code
def smallestMissingMultiple(nums, k):
num_set = set(nums)
multiple = k
while multiple in num_set:
multiple += k
return multipleFrequently Asked Questions
What is the Smallest Missing Multiple of K problem?
Given an integer array nums and an integer k, find the smallest positive multiple of k that is not present in the array. Return this value.
How do you solve Smallest Missing Multiple of K?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Smallest Missing Multiple of K?
Smallest Missing Multiple of K is asked at Microsoft. It is a easy difficulty problem.
What are common mistakes on Smallest Missing Multiple of K?
- Clarify whether k itself could be missing from the array.
- Handle edge case where k is 0 — discuss assumptions with interviewer.
- The set approach is simplest and runs in O(n + m/k) time where m is the answer.
- Do not confuse with finding the smallest missing positive integer overall.
- Confirm that all multiples checked must be positive.