Problem Statement in English

You are given a 0-indexed integer array nums and an integer value.

In one operation, you can choose an index i such that 0 <= i < nums.length and update nums[i] to be either nums[i] + value or nums[i] - value.

Return the smallest non-negative integer that cannot be obtained from nums by applying the mentioned operation any number of times (possibly zero).

Approach

The idea is to use a hashmap to store the frequency of each element in the array after converting all elements to their smallest equivalent non-negative values modulo value.

Then we know that the answer will be in the range [0, len(nums)] because if all len(nums) - 1 elements are present then the answer will be len(nums). Otherwise it will be the first missing element in the range.

So we iterate from 0 to len(nums) and check if the element’s modulo is present in the hashmap.

If it is present we decrement its frequency by 1 (because we are essentially using up an element from the nums array). If it is not present then we return that element as the answer, since that’s the missing number.

Solution in Python


class Solution:
    def findSmallestInteger(self, nums: List[int], value: int) -> int:
        hm = defaultdict(int)

        for n in nums:
            if n < 0:
                d = ceil(-n / value)
                n += d * value
            else:
                d = floor(n / value)
                n -n= d * value

            hm[n] += 1

        for i in range(len(nums)):
            r = i % value
            if hm[r]:
                hm[r] -= 1
            else:
                return i

        return len(nums)

Complexity

  • Time: $O(n)$
    Since we iterate over the array once.

  • Space: $O(n)$
    For the hashmap used to store the frequency of each element.

And we are done.