EasyArrayHash TableUpdated Sep 2026

3718. Smallest Missing Multiple of K

Asked at Microsoft

Difficulty

Easy

Time

O(n + m)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given an array of integers nums and an integer k. A multiple of k is any positive number you can get by multiplying k by 1, 2, 3, and so on (so k, 2k, 3k, ...).

Return the smallest positive multiple of k that does not appear in nums. Values in nums that are not multiples of k are irrelevant and can be ignored.

If nums happens to contain every multiple of k up to some point, keep walking forward — the answer is simply the next multiple after the last one you found.

Which multiples are already there?

nums8234601234The green cells are the multiples of 2: 8, 2, 4 and 6.The 3 is not a multiple.multiples of 2246810120123452, 4, 6 and 8 are present; 10 is the first onemissing, so the answer is 10.
For k = 2 we walk the multiples 2, 4, 6, 8, 10 and stop at the first one the array does not contain.

Constraints

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

Examples

Example 1
Inputnums = [8,2,3,4,6], k = 2
Output10
WhyThe multiples of 2 in order are 2, 4, 6, 8, 10, ... The array contains 2, 4, 6 and 8, so the first one missing is 10.
Example 2
Inputnums = [1,4,7,10,15], k = 5
Output5
WhyThe multiples of 5 are 5, 10, 15, ... The array has 10 and 15 but not 5, so the smallest missing multiple is 5.

Asked At

1 companies
CompanyDifficulty
MicrosoftEasyView all Microsoft questions →

How to Think About It

1

Brute force: check k, 2k, 3k, ... in order and return the first multiple not in nums.

2

Convert nums to a set for O(1) lookups and iterate through multiples of k.

3

Sort the array first and use binary search for each candidate multiple.

4

Optimal: use a hash set and enumerate multiples of k starting from k itself until one is missing.

5

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.

Hash set plus a walk over multiples

build set from numscandidate = kwhile candidate in set: candidate += kreturn candidateThe loop stops the moment a multiple is not in theset.candidates24681001234answerEach green candidate was found in the set; 10 was not,so the loop ends and returns 10.set = {8, 2, 3, 4, 6}2 in set → 4 in set → 6 in set → 8 in set10 not in set → answer = 10
Put every number in a set, then test k, 2k, 3k, ... until a test fails.
ComplexityTime O(n + m)Space O(n)n is the array length and m is how many multiples we check before finding a missing one (at most n + 1). Building the set costs O(n), and each lookup is O(1).

What Trips People Up in Real Interviews

1

Clarify whether k itself could be missing from the array.

2

Handle edge case where k is 0 — discuss assumptions with interviewer.

3

The set approach is simplest and runs in O(n + m/k) time where m is the answer.

4

Do not confuse with finding the smallest missing positive integer overall.

5

Confirm that all multiples checked must be positive.

Solution Code

O(n + m) time
def smallestMissingMultiple(nums, k):
    num_set = set(nums)
    multiple = k
    while multiple in num_set:
        multiple += k
    return multiple

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n + m) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.