Smallest Missing Non-negative Integer After Operations

Smallest Missing Non-negative Integer After Operations - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,10,3], value = 6

› Output: 2

💡 Note: We can transform: 1→1 (no change), 10→4 (subtract 6), 3→3 (no change). This gives us array [1,4,3]. We can also get [1,4,9] by 3→9 (add 6). The MEX of [1,4,3] is 0, MEX of [1,4,9] is 0. But we can make [7,4,3] (1→7) which has MEX=0. Actually, we can make values 1 and 3 with remainder 1 and 3 mod 6, so we can fill some positions to get MEX=2.

Example 2 — Zero Value

$ Input: nums = [3,4,1,9], value = 0

› Output: 0

💡 Note: When value=0, we cannot transform any elements. The array remains [3,4,1,9]. The MEX is 0 since 0 is not present.

Example 3 — Perfect Consecutive

$ Input: nums = [0,1,4,5], value = 3

› Output: 4

💡 Note: We can transform: 0→0, 1→1, 4→1 (subtract 3), 5→2 (subtract 3). This gives remainders 0,1,1,2 mod 3. We can make consecutive sequence [0,1,2,3] by using the elements optimally.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹
1 ≤ value ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,10,3] with value=6 for add/subtract operations

Transform

Group elements by remainder modulo 6: {1→1, 4→1, 3→1}

Maximize MEX

Build longest consecutive sequence from 0 using available remainders

Key Takeaway

🎯 Key Insight: Elements with the same remainder modulo value can be freely interchanged through operations

Asked in

G Google 15 f Meta 12 a Amazon 8 M Microsoft 6

The key insight is that elements can be transformed to the same final value if their difference is divisible by value. Group elements by remainder when divided by value, then greedily build the longest consecutive sequence starting from 0. Best approach uses modular arithmetic grouping. Time: O(n), Space: O(min(n, value))

Common Approaches

Approach	Time	Space	Notes
✓ Modular Grouping	O(n log n)	O(n)	Group elements by their remainder when divided by value, then greedily assign to create consecutive sequence
Try All Possible Transformations	O(k^n × n)	O(k^n)	Generate all possible arrays by applying operations and find the maximum MEX
Optimal Greedy Assignment	O(n)	O(min(n, value))	Use mathematical insight that elements with same remainder modulo value can be freely interchanged

Modular Grouping — Algorithm Steps

Group elements by remainder (num % value)
Sort groups by remainder
Greedily assign each group to consecutive positions
Return length of achievable consecutive sequence

Visualization

Tap to expand

Step-by-Step Walkthrough

Group

Group elements by remainder when divided by value

Sort

Sort groups by remainder value

Assign

Greedily assign groups to consecutive positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct Group {
    int remainder;
    int count;
};

int compare(const void* a, const void* b) {
    return ((struct Group*)a)->remainder - ((struct Group*)b)->remainder;
}

int solution(int* nums, int numsSize, int value) {
    if (value == 0) {
        bool existing[100001] = {false};
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] >= 0 && nums[i] <= 100000) {
                existing[nums[i]] = true;
            }
        }
        int mex = 0;
        while (mex <= 100000 && existing[mex]) {
            mex++;
        }
        return mex;
    }
    
    int groups[1001] = {0};
    for (int i = 0; i < numsSize; i++) {
        int remainder = ((nums[i] % value) + value) % value;
        groups[remainder]++;
    }
    
    struct Group sortedGroups[1001];
    int groupCount = 0;
    for (int i = 0; i < 1001; i++) {
        if (groups[i] > 0) {
            sortedGroups[groupCount].remainder = i;
            sortedGroups[groupCount].count = groups[i];
            groupCount++;
        }
    }
    
    qsort(sortedGroups, groupCount, sizeof(struct Group), compare);
    
    int mex = 0;
    for (int i = 0; i < groupCount; i++) {
        if (sortedGroups[i].remainder == mex % value) {
            mex += sortedGroups[i].count;
        } else {
            break;
        }
    }
    
    return mex;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int value;
    scanf("%d", &value);
    
    int result = solution(nums, numsSize, value);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Grouping takes O(n), sorting groups takes O(k log k) where k ≤ n

⚡ Linearithmic

Space Complexity

O(n)

Hash map stores all elements grouped by remainder

⚡ Linearithmic Space

4.2K Views

Medium Frequency

~25 min Avg. Time

185 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Modular Grouping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler