# Smallest Missing Non-negative Integer After Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-missing-non-negative-integer-after-operations)
Canonical: https://scaleengineer.com/dsa/problems/smallest-missing-non-negative-integer-after-operations
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [IBM](https://scaleengineer.com/companies/ibm), [Mercari](https://scaleengineer.com/companies/mercari)
---
## 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 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`

# Approaches
## Brute-Force Simulation by Modifying a List
This approach directly simulates the process of forming the target sequence `0, 1, 2, ...`. It first converts all numbers to their base remainders modulo `value` and then, for each target number `k`, it searches the entire list of available remainders to see if `k % value` can be found. If found, the remainder is consumed, and the process continues to `k+1`.
**Time:** O(N^2), where N is the length of `nums`. The outer `while` loop can run up to N times. Inside the loop, both searching and removing an element from an `ArrayList` take O(K) time, where K is the current size of the list. In the worst case, this is O(N), leading to a total complexity of O(N*N). · **Space:** O(N), where N is the length of `nums`. An auxiliary list `remainders` is created to store the remainders of all N elements.
**Pros:** Conceptually simple to understand.; Directly simulates the process of finding and using numbers.
**Cons:** Inefficient for large inputs due to the quadratic time complexity.; Repeatedly scanning and modifying the list is slow.
### Explanation
The fundamental insight is that a number `num` can be transformed into any other number `num'` if and only if they share the same remainder when divided by `value` (i.e., `num ≡ num' (mod value)`). This is because any operation adds or subtracts a multiple of `value`, which does not change the remainder.

This approach leverages this by first creating a list of the non-negative remainders of all numbers in the input `nums` array. Then, it attempts to greedily construct the sequence of non-negative integers starting from 0. It checks for `mex = 0`, then `mex = 1`, and so on. To check if a given `mex` can be formed, it scans the list of remainders to find an element equal to `mex % value`. If such an element is found, it's removed from the list (to signify it has been used), and the `mex` is incremented. The process stops when a required remainder is not found in the list. The current value of `mex` is then the smallest missing non-negative integer that cannot be formed, which is the answer.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int smallestEqualValue(int[] nums, int value) {
        List<Integer> remainders = new ArrayList<>();
        for (int num : nums) {
            remainders.add((num % value + value) % value);
        }

        int mex = 0;
        while (true) {
            int targetRemainder = mex % value;
            // .remove(Object) is O(N), so this loop is N*N
            if (remainders.remove(Integer.valueOf(targetRemainder))) {
                mex++;
            } else {
                break;
            }
        }
        return mex;
    }
}
```
### Algorithm
- Create a new `ArrayList` called `remainders`.
- Iterate through `nums` and for each `num`, add its non-negative remainder `(num % value + value) % value` to the `remainders` list.
- Initialize `mex = 0`.
- Start an infinite loop.
- In the loop, search for the value `mex % value` within the `remainders` list.
- If it is found, remove one occurrence of it from the list and increment `mex`.
- If it is not found, the current `mex` cannot be formed, so break the loop.
- Return the final `mex` value.

## Optimal Approach using a Remainder Frequency Map
This efficient approach avoids the costly repeated searches by pre-calculating the frequencies of all possible remainders (`0` to `value-1`). By storing these counts in an array, we can check for the availability of a required remainder in constant time, leading to a linear time solution.
**Time:** O(N + value), where N is the length of `nums`. Initializing the `counts` array takes O(value). Populating it takes O(N). The final `while` loop to find the MEX runs at most N+1 times (as `mex` can't exceed N), and each step is an O(1) array access. Thus, the total time is O(N + value). · **Space:** O(value). We use an auxiliary array `counts` of size `value` to store the frequencies of the remainders.
**Pros:** Highly efficient with a linear time complexity of O(N + value).; Simple and clean implementation.
**Cons:** Requires O(value) extra space, which could be significant if `value` is very large.
### Explanation
This approach is based on the same core principle: we need to form the sequence `0, 1, 2, ...`, and to form a number `k`, we need an original number from `nums` whose remainder modulo `value` is `k % value`.

The key optimization is to count the occurrences of each remainder in a single pass. We use an auxiliary array, `counts`, of size `value`. `counts[r]` stores how many numbers in `nums` have a remainder of `r`.

After populating this frequency map, we can determine the maximum MEX. We iterate `mex` from `0` upwards. For each `mex`, we find the required remainder `r = mex % value`. We then check our `counts` array at index `r`. If `counts[r]` is greater than zero, it means we have a number we can use. We decrement `counts[r]` (to mark it as used) and increment `mex` to try to form the next integer. If `counts[r]` is zero, we lack the necessary number to form `mex`, so `mex` is our answer. This check is an O(1) operation, making the entire process very fast.

```java
class Solution {
    public int smallestEqualValue(int[] nums, int value) {
        int[] counts = new int[value];
        for (int num : nums) {
            int remainder = (num % value + value) % value;
            counts[remainder]++;
        }

        int mex = 0;
        while (counts[mex % value] > 0) {
            counts[mex % value]--;
            mex++;
        }
        
        return mex;
    }
}
```
### Algorithm
- Create an integer array `counts` of size `value` and initialize it with zeros.
- Iterate through the `nums` array. For each `num`, calculate its non-negative remainder `r = (num % value + value) % value` and increment `counts[r]`.
- Initialize `mex = 0`.
- Use a `while` loop that continues as long as we have numbers for the current `mex`. The condition is `counts[mex % value] > 0`.
- Inside the loop, decrement `counts[mex % value]` to use up one number, and then increment `mex`.
- The loop terminates when `counts[mex % value]` is 0, meaning `mex` cannot be formed. Return `mex`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
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

```