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 arrayInput: 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 approachimport 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 numberdef 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 Codeif __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 approachusing 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 codepublic 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 numberfunction 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
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
