Smallest Missing Multiple of K

Difficulty: Easy | Acceptance: 63.20% | Paid: No Topics: Array, Hash Table

You are given an integer array nums and an integer k. Return the smallest positive integer x such that x is a multiple of k and x is not present in nums.

• Examples
• Constraints
• Brute Force
• Hash Set
• Sorting

Examples

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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹

Brute Force

Intuition Iterate through the multiples of k starting from k. For each multiple, check if it exists in the array by scanning the entire array.

Steps

• Initialize x = k.
• Loop while true:
  • Check if x exists in nums.
  • If not, return x.
  • Increment x by k.

class Solution:
    def findSmallestInteger(self, nums: List[int], k: int) -> int:
        x = k
        while True:
            found = False
            for num in nums:
                if num == x:
                    found = True
                    break
            if not found:
                return x
            x += k

Complexity

• Time: O(N * M), where N is the length of nums and M is the value of the result divided by k.
• Space: O(1)
• Notes: This approach is inefficient for large arrays or large missing values.

Hash Set

Intuition Store the elements of nums in a hash set to allow O(1) lookups. Then iterate through multiples of k and check for existence in the set.

Steps

• Create a set from nums.
• Initialize x = k.
• Loop while true:
  • If x is not in the set, return x.
  • Increment x by k.

class Solution:
    def findSmallestInteger(self, nums: List[int], k: int) -> int:
        num_set = set(nums)
        x = k
        while True:
            if x not in num_set:
                return x
            x += k

Complexity

• Time: O(N + M), where N is the length of nums and M is the value of the result divided by k.
• Space: O(N)
• Notes: This is the optimal approach for this problem.

Sorting

Intuition Sort the array first. Then iterate through multiples of k and use binary search to check if the multiple exists in the sorted array.

Steps

• Sort nums.
• Initialize x = k.
• Loop while true:
  • Perform binary search for x in nums.
  • If not found, return x.
  • Increment x by k.

class Solution:
    def findSmallestInteger(self, nums: List[int], k: int) -> int:
        nums.sort()
        x = k
        while True:
            # Binary search
            left, right = 0, len(nums) - 1
            found = False
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == x:
                    found = True
                    break
                elif nums[mid] < x:
                    left = mid + 1
                else:
                    right = mid - 1
            if not found:
                return x
            x += k

Complexity

• Time: O(N log N + M log N), where N is the length of nums and M is the value of the result divided by k.
• Space: O(1) or O(N) depending on the sorting algorithm.
• Notes: Less efficient than the Hash Set approach due to the sorting overhead.