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

Solutions

Solution 1: Counting

We use a hash table \(\textit{cnt}\) to count the number of remainders when each number in the array is modulo \(\textit{value}\).

Then we traverse starting from \(0\). For the current number \(i\) being traversed, if \(\textit{cnt}[i \bmod \textit{value}]\) is \(0\), it means there is no number in the array whose remainder when modulo \(\textit{value}\) is \(i\), so \(i\) is the MEX of the array, and we can return it directly. Otherwise, we decrement \(\textit{cnt}[i \bmod \textit{value}]\) by \(1\) and continue traversing.

The time complexity is \(O(n)\) and the space complexity is \(O(\textit{value})\), where \(n\) is the length of array \(\textit{nums}\).

Python3JavaC++GoTypeScriptRustJavaScript

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

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;
            }
        }
    }
}

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;
            }
        }
    }
};

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]--
    }
}

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;
        }
    }
}

impl Solution {
    pub fn find_smallest_integer(nums: Vec<i32>, value: i32) -> i32 {
        let mut cnt = vec![0; value as usize];
        for &x in &nums {
            let idx = ((x % value + value) % value) as usize;
            cnt[idx] += 1;
        }

        let mut i = 0;
        loop {
            let idx = (i % value) as usize;
            if cnt[idx] == 0 {
                return i;
            }
            cnt[idx] -= 1;
            i += 1;
        }
    }
}

/**
 * @param {number[]} nums
 * @param {number} value
 * @return {number}
 */
var findSmallestInteger = function (nums, value) {
    const cnt = 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;
        }
    }
};

2598. Smallest Missing Non-negative Integer After Operations

Description

Solutions

Solution 1: Counting

Comments