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!
