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)