Find the MEX of given Array

Mex of an array is the smallest non-negative integer that does not appear in the array.

Given an array of non-negative integers, find mex of its elements.

Examples :

Input : arr[] = {0, 3, 1, 2}
Output : 4
All integers smaller than 4, i.e. 0, 1, 2 and 3 are 
present in the array. Hence mex of this array is 4.

Input : arr[] = {4, 0, 1, 5, 7, 6}
Output : 2
2 is the smallest non-negative integer that does not
appear in the array. 

Input : arr[] = {5, 9}
Output : 0

Approach:

Start with mex set to 0, our goal is finding the missing value.
Arrange arr in ascending order using std::sort for easy checking.
Use a loop to go through each element from 0 to n-1.
Inside the loop, compare arr[i] to the current mex value.
If arr[i] equals mex, increase mex by 1. This helps find the missing value.
Repeat steps 4 and 5 for all sorted elements. Mex holds the missing value.
Return mex as the result. It’s the smallest missing non-negative number.
In an example with {3, 6, 0, 4, 1, 9, 2}, it sorts to {0, 1, 2, 3, 4, 6, 9}.
Mex is found to be 5, the smallest missing non-negative integer.

Implementation:

C++

// C++ Program to find mex of a given array
#include <bits/stdc++.h>
using namespace std;

// function to return mex of elements
// of an array of size n
int findMex(int arr[], int n)
{
    // initialize mex
    int mex = 0;

    // sort the array to traverse the elements in
    // increasing order
    sort(arr, arr + n);

    // Iterate through all elements and check if the mex
    // is present. If present then increase mex by 1
    for (int i = 0; i < n; i++) {
        if (arr[i] == mex)
            mex++;
    }
    return mex;
}

// Driver code
int main()
{
    int arr[] = { 3, 6, 0, 4, 1, 9, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Mex of given array is " << findMex(arr, n);
    return 0;
}

Java

// Java Program to find mex of a given array
import java.util.Arrays;

class Cpp {
    static int arr[] = { 3, 6, 0, 4, 1, 9, 2 };

    // method to find mex of elements of an array
    static int findMex()
    {
        // initialize mex
        int mex = 0;

        // sort the array to traverse the elements in
        // increasing order
        Arrays.sort(arr);

        // Iterate through all elements and check if the mex
        // is present. If present then increase mex by 1
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == mex)
                mex++;
        }
        return mex;
    }

    // Driver method
    public static void main(String[] args)
    {
        System.out.println("Mex of given array is "
                           + findMex());
    }
}

Python

# Python code to find mex of a given array
def findMex(arr, n):

    # initialize mex
    mex = 0

    # sort the array to traverse the elements initialize
    # increasing order
    arr.sort()

    # iterate through all elements and check if the mex
    # is present. If present then increase mex by 1
    for i in range(0, n):
        if arr[i] == mex:
            mex += 1
    return mex


# driver function
arr = [3, 6, 0, 4, 1, 9, 2]

# calculating length of array
n = len(arr)

ans = findMex(arr, n)

# print mex
print 'Mex of given array is', ans

Output :

Mex of given array is 5

Time Complexity: O(nLogn)