Skip to content

2598. Smallest Missing Non-negative Integer After Operations

Description

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

In one operation, you can add or subtract value from any element of nums.

  • For example, if nums = [1,2,3] and value = 2, you can choose to subtract value from nums[0] to make nums = [-1,2,3].

The MEX (minimum excluded) of an array is the smallest missing non-negative integer in it.

  • For example, the MEX of [-1,2,3] is 0 while the MEX of [1,0,3] is 2.

Return the maximum MEX of nums after applying the mentioned operation any number of times.

 

Example 1:

Input: nums = [1,-10,7,13,6,8], value = 5
Output: 4
Explanation: One can achieve this result by applying the following operations:
- Add value to nums[1] twice to make nums = [1,0,7,13,6,8]
- Subtract value from nums[2] once to make nums = [1,0,2,13,6,8]
- Subtract value from nums[3] twice to make nums = [1,0,2,3,6,8]
The MEX of nums is 4. It can be shown that 4 is the maximum MEX we can achieve.

Example 2:

Input: nums = [1,-10,7,13,6,8], value = 7
Output: 2
Explanation: One can achieve this result by applying the following operation:
- subtract value from nums[2] once to make nums = [1,-10,0,13,6,8]
The MEX of nums is 2. It can be shown that 2 is the maximum MEX we can achieve.

 

Constraints:

  • 1 <= nums.length, value <= 105
  • -109 <= nums[i] <= 109

Solutions

Solution 1: Count

We use a hash table or array \(cnt\) to count the number of times each remainder of \(value\) is taken modulo in the array.

Then start from \(0\) and traverse, for the current number \(i\) traversed, if \(cnt[i \bmod value]\) is \(0\), it means that there is no number in the array that takes \(i\) modulo \(value\) as the remainder, then \(i\) is the MEX of the array, and return directly. Otherwise, reduce \(cnt[i \bmod value]\) by \(1\) and continue to traverse.

The time complexity is \(O(n)\) and the space complexity is \(O(value)\). Where \(n\) is the length of the array \(nums\).

1
2
3
4
5
6
7
class Solution:
    def findSmallestInteger(self, nums: List[int], value: int) -> int:
        cnt = Counter(x % value for x in nums)
        for i in range(len(nums) + 1):
            if cnt[i % value] == 0:
                return i
            cnt[i % value] -= 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int findSmallestInteger(int[] nums, int value) {
        int[] cnt = new int[value];
        for (int x : nums) {
            ++cnt[(x % value + value) % value];
        }
        for (int i = 0;; ++i) {
            if (cnt[i % value]-- == 0) {
                return i;
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        int cnt[value];
        memset(cnt, 0, sizeof(cnt));
        for (int x : nums) {
            ++cnt[(x % value + value) % value];
        }
        for (int i = 0;; ++i) {
            if (cnt[i % value]-- == 0) {
                return i;
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func findSmallestInteger(nums []int, value int) int {
    cnt := make([]int, value)
    for _, x := range nums {
        cnt[(x%value+value)%value]++
    }
    for i := 0; ; i++ {
        if cnt[i%value] == 0 {
            return i
        }
        cnt[i%value]--
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function findSmallestInteger(nums: number[], value: number): number {
    const cnt: number[] = new Array(value).fill(0);
    for (const x of nums) {
        ++cnt[((x % value) + value) % value];
    }
    for (let i = 0; ; ++i) {
        if (cnt[i % value]-- === 0) {
            return i;
        }
    }
}

Comments