Problem

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 ofnums after applying the mentioned operationany number of times.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5

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^5
  • -109 <= nums[i] <= 10^9

Solution

Method 1 – Remainder Bucketing (Greedy)

Intuition

Since we can add or subtract value any number of times to any element, each number can be mapped to its remainder modulo value. For each remainder, the number of unique values we can create is limited by how many times that remainder appears. The maximum MEX is the smallest non-negative integer that cannot be formed by using the available remainders.

Approach

  1. For each number in nums, compute its remainder modulo value (make it non-negative).
  2. Count the frequency of each remainder.
  3. For each integer starting from 0, check if the corresponding remainder bucket has enough elements to form that integer (i.e., for i, check if count[i % value] > i // value).
  4. The first integer for which this is not true is the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

import java.util.*;
class Solution {
    public int findSmallestInteger(int[] nums, int value) {
        int[] cnt = new int[value];
        for (int x : nums) {
            int r = ((x % value) + value) % value;
            cnt[r]++;
        }
        for (int i = 0; ; ++i) {
            if (cnt[i % value] == 0) return i;
            cnt[i % value]--;
        }
    }
}
1
2
3
4
5
6
7
8
9

from collections import Counter
class Solution:
    def findSmallestInteger(self, nums, value):
        cnt = Counter((x % value + value) % value for x in nums)
        i = 0
        while True:
            if cnt[i % value] == 0:
                return i
            cnt[i % value] -= 1

Complexity

  • ⏰ Time complexity: O(n + M), where n = len(nums), M is the answer (at most n + value).
  • 🧺 Space complexity: O(value) for the remainder buckets.