We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Missing Non-negative Integer After Operations

Number: 2661

Difficulty: Medium

Paid? No

Companies: IBM, Atlassian, Mercari

Problem Description

Given an integer array nums and an integer value, you can add or subtract value from any element any number of times. Because adding or subtracting value does not change the element's remainder when divided by value, the only invariant is the modulo value of each element. The task is to determine the maximum possible MEX (minimum excluded non-negative integer) obtainable after applying the operations optimally.

Key Insights

  • Any operation on an element will keep its remainder modulo value unchanged.
  • Group numbers by their remainder (i.e. for r = nums[i] modulo value).
  • For a target number x, its remainder is x mod value. One can create x from an element with remainder r if the number of elements in that group exceeds how many times we already "used" that remainder. Specifically, for x = q * value + r, we require that we have at least q + 1 numbers with remainder r.
  • Use a greedy strategy. Start from x = 0 and check incrementally if x can be represented. The first x that fails is the MEX.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of nums and m is the value (since we iterate as long as possible until we find the MEX; note m is bounded by the counts in the remainder groups).
Space Complexity: O(m), for storing frequency counts for each remainder mod value.

Solution

The solution uses a greedy method by leveraging the invariant that each element’s modulo value is fixed despite operations. We first calculate the frequency of each remainder when dividing the numbers in nums by value. Then, starting from 0, for each number x, we check if an element with remainder x mod value is available in sufficient quantity. Specifically, for x = (q * value + r), we require that there are at least q + 1 elements in the bucket for remainder r. We increment x as long as the condition is met and stop when x cannot be constructed. This x will be the maximum MEX obtainable.

Code Solutions

# Python code solution for "Smallest Missing Non-negative Integer After Operations"

def findSmallestMissing(nums, value):
    # frequency array for remainders 0 to value-1, initial count is 0 for each remainder
    remainder_counts = [0] * value
    
    # Populate frequency counts: each element's mod value is invariant under operations
    for num in nums:
        remainder = num % value
        remainder_counts[remainder] += 1
        
    mex = 0  # start checking from 0 upwards
    # Greedily determine the maximum MEX achievable
    while True:
        # r is the required remainder for the current mex candidate
        r = mex % value
        # For current mex = q*value + r, we need at least (q+1) numbers with remainder r.
        if remainder_counts[r] > (mex // value):
            mex += 1  # it is possible to represent mex, try next
        else:
            # We cannot represent mex, so we've found the MEX
            break
    
    return mex

# Example Usage:
nums = [1, -10, 7, 13, 6, 8]
value = 5
print(findSmallestMissing(nums, value))  # Output should be 4
← Back to All Questions