Find the MEX of given Array

0 0 3 minutes read

You are given an array arr[] of size N, the task is to determine the MEX of the array.

MEX is the smallest whole number that is not present in the array.

Examples:

Input: arr[] = {1, 0, 2, 4}
Output: 3
Explanation: 3 is the smallest whole number that is not present in the array

Input: arr[] = {-1, -5, 0, 4}
Output: 1
Explanation: 1 is the smallest whole number that is missing in the array.

Approach: Follow the below idea to solve the problem

Sort the array in increasing order and find the first number starting from 0 which is not present in the array.

Follow the steps to solve the problem:

Sort the array.
Initialize a variable mex = 0.
Travel over the array from index 0 to N-1.
If the element is equal to mex
- Increment mex by 1 i.e., mex = mex + 1
- Else continue the iteration
Return mex as the final answer.

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
int mex(vector<int> &arr, int N)
{
 
  // sort the array
  sort(arr.begin(), arr.end());
 
  int mex = 0;
  for (int idx = 0; idx < N; idx++)
  {
    if (arr[idx] == mex)
    {
      // Increment mex
      mex += 1;
    }
  }
 
  // Return mex as answer
  return mex;
}
 
int main()
{
  vector<int> arr = {1, 0, 2, 4};
  int N = arr.size();
 
  // Function call
  cout << mex(arr, N) << endl;
  return 0;
}
 
// This code is contributed by ishankhandelwals.

Java

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
 
  static int mex(int[] arr, int N)
  {
     
    // sort the array
    Arrays.sort(arr);
 
    int mex = 0;
    for (int idx = 0; idx < N; idx++) {
      if (arr[idx] == mex) {
        // Increment mex
        mex += 1;
      }
    }
 
    // Return mex as answer
    return mex;
  }
 
  public static void main(String[] args)
  {
    int[] arr = { 1, 0, 2, 4 };
    int N = arr.length;
 
    // Function call
    System.out.print(mex(arr, N));
  }
}
 
// This code is contributed by lokeshmvs21.

Python3

# Python code to implement the approach
 
# Function to find smallest
# Positive missing number
def mex(arr, N):
 
    # Sort the array
    arr.sort()
     
    mex = 0
    for idx in range(N):
        if arr[idx] == mex:
 
            # Increment mex
            mex += 1
 
    # return mex as answer
    return mex
 
 
# Driver Code
if __name__ == '__main__':
 
    # Given Input
    arr = [1, 0, 2, 4]
    N = len(arr)
 
    # Function Call
    print(mex(arr, N))

C#

// C# code to implement the above approach
using System;
 
class GFG {
 
  static int mex(int[] arr, int N)
  {
     
    // sort the array
    Array.Sort(arr);
 
    int mex = 0;
    for (int idx = 0; idx < N; idx++) {
      if (arr[idx] == mex) {
        // Increment mex
        mex += 1;
      }
    }
 
    // Return mex as answer
    return mex;
  }
 
// Driver code
public static void Main()
{
     int[] arr = { 1, 0, 2, 4 };
    int N = arr.Length;
 
    // Function call
    Console.Write(mex(arr, N));
}
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
     
   // JavaScript code for the above approach
 
// Function to find smallest
// Positive missing number
function mex(arr, N){
   
    // Sort the array
    arr.sort();
       
    let mex = 0;
    let idx = 0;
    for(idx = 0; idx < N; idx++){
        if (arr[idx] == mex){
   
            // Increment mex
            mex += 1;
            }
      }
    // return mex as answer
    return mex;
  }
 
    // Driver code
     
    // Given Input
    let arr = [1, 0, 2, 4];
    let N = arr.length;
   
    // Function Call
    document.write(mex(arr, N));
     
    // This code is contributed by code_hunt.
</script>

Output

Time Complexity: O(N * logN)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!