Smallest Missing Non-negative Integer After Operations

main.md

Question

Approach

I observe that every number can be transformed to any integer having the same residue modulo value (by adding/subtracting value repeatedly). So each element only contributes one token to its residue class r = x % value. To maximize the MEX we need to be able to form all integers 0,1,2,...,m-1. Forming integer i requires consuming one token from residue i % value. Thus I count how many tokens we have per residue, then greedily try to form integers i = 0,1,2,...: for each i I check whether counts[i % value] > 0; if yes I consume one and continue, otherwise the current i is the MEX.

Implementation

class Solution:
    def findSmallestInteger(self, nums: List[int], value: int) -> int:
        counts = [0] * value
        for x in nums:
            counts[x % value] += 1

        mex = 0
        while counts[mex % value] > 0:
            counts[mex % value] -= 1
            mex += 1
        return mex

Complexities

• Time: O(n + value) — building residue counts is O(n), the greedy loop runs at most n iterations
• Space: O(value) for the residue counts array