DDSA Solutions

3718. Smallest Missing Multiple of K

EasyView on LeetCode
ArrayHash Tableenumeration

Problem Overview

The answer is the smallest positive multiple of k that does not appear in nums.

Intuition

The answer is the smallest positive multiple of k that does not appear in nums. Constraints cap every nums[i] at 100, so a boolean table of size 101 records presence. Then try k, 2k, 3k, ... The first multiple that is unmarked, or that is already larger than 100, cannot sit in the array.

Algorithm

  1. 1Allocate s[101] = false. For each x in nums, if x < 101 set s[x] = true.
  2. 2For i = 1, 2, 3, ... let x = k * i.
  3. 3If x >= 101 or s[x] is false, return x.

Example Walkthrough

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

  1. 1.Mark 2, 3, 4, 6, 8.
  2. 2.2, 4, 6, 8 are present. 10 is larger than any possible nums[i] (or unmarked), so 10 is missing.

Output: 10

Common Pitfalls

  • •Ignore values >= 101 if they ever appear; under the stated constraints they do not.
  • •Do not return k without checking whether k itself is in nums.
  • •The loop is over multiples, not over nums a second time.
  • •k itself can be 100. Then 100 may be present and the answer is 200, which the x >= 101 branch covers.
3718.cs
C#
// Approach: Mark values that appear (values are at most 100). Then walk
// k, 2k, 3k, ... and return the first multiple that is unmarked or larger
// than 100, since that multiple cannot be in nums.
// Complexity: O(n) time and O(1) extra space (fixed table of size 101).
public class Solution
{
    public int MissingMultiple(int[] nums, int k)
    {
        bool[] s = new bool[101];
        foreach (int x in nums)
        {
            if (x < s.Length)
                s[x] = true;
        }
        for (int i = 1; ; ++i)
        {
            int x = k * i;
            if (x >= s.Length || !s[x])
                return x;
        }
    }
}
Was this solution helpful?

Related Problems