Partition the given array in two parts to make the MEX of both parts same
Given an array arr[] containing N integers where 0 ≤ A[ i ] ≤ N, the task is to divide the array into two equal parts such that the MEX of both the parts are the same, otherwise print -1.
Note: The MEX (minimum excluded) of an array is the smallest non-negative integer that does not exist in the array.
Examples:
Input: N = 6, arr[] = {1, 6, 2, 3, 5, 2}
Output:
0
1 2 5
2 3 6
Explanation: After dividing the given array into {1, 2, 5} and {2, 3, 6}, MEX of both array is equal( i. e MEX = 0)Input: N = 4, arr[] = {0, 0, 1, 2}
Output: -1
Explanation: Not possible to divide an array into two different array
Intuition: As mentioned, MEX is the smallest non-negative integer that does not belong to the array. So any non-negative smallest number which is not present in the given array can become the MEX for both output arrays.
To make an integer X, MEX for both arrays, all elements less than X must present at least once in both the output array.
For Example:
Array = [1, 4, 2, 4, 2, 1, 1]
Then divide the array into [1, 1, 2, 4] and [1, 2, 4]
If any element less than X is present in the given array only once, then it is not possible to divide the given array into two arrays of equal MEX.
Example:
Array = [1, 2, 3, 4, 4, 2, 1]
In this example, 3 is only present 1 time in given array so if we try to divide it into 2 array, then MEX of both array is not equal.
[1, 2, 3, 4] : MEX = 5
[1, 2, 4] : MEX = 3
Approach: The solution to the problem is based on the concept of hashmap. Follow the steps mentioned below:
- Create a hash map to check whether any unique element is present in the array or not.
- Iterate from 0 to N and in each iteration check
- If the frequency of that element is 1, then it is not possible to divide the array into two such that their MEX should be equal
- If the frequency of that element is 0, then we can divide the array.
- If the frequency of that element is more than 1, then check for the next element.
- Sort the given array and divide the array according to its even or odd index, so that if any element is present 2 or more than 2 times in the array then after dividing both output array consists at least 1 time that elements to maintain equal MEX.
- Print both the arrays.
Below is the code implementation:
C++
// C++ code to implement the above approach: #include <bits/stdc++.h> using namespace std; // Function to find the // Least common missing no. void MEX_arr( int * A, int N) { unordered_map< int , int > mp; bool status = true ; // Push all array elements // Into unordered_map for ( int i = 0; i < N; i++) { mp[A[i]]++; } // Check any unique element is present // In array or any element // Which is not array; for ( int i = 0; i <= N; i++) { if (mp[i] == 0) { cout << i << "\n" ; break ; } if (mp[i] == 1) { status = false ; break ; } } if (status == true ) { // Sort the array sort(A, A + N); int A1[N / 2], A2[N / 2]; // Push all elements at even index // in first array and at odd index // into another array for ( int i = 0; i < N / 2; i++) { A1[i] = A[2 * i]; A2[i] = A[2 * i + 1]; } // Print both the arrays for ( int i = 0; i < N / 2; i++) { cout << A1[i] << " " ; } cout << "\n" ; for ( int i = 0; i < N / 2; i++) { cout << A2[i] << " " ; } } // If not possible to divide // into two array, print -1 else cout << -1; } // Driver code int main() { int N = 6; int arr[N] = { 1, 6, 2, 3, 5, 2 }; unordered_map< int , int > mp; // Function call MEX_arr(arr, N); return 0; } |
Java
// Java code to implement the above approach import java.io.*; import java.util.*; class GFG { // Function to find the // Least common missing no. public static void MEX_arr( int A[], int N) { HashMap<Integer, Integer> mp = new HashMap<>(); boolean status = true ; // Push all array elements // Into HashMap for ( int i = 0 ; i < N; i++) { if (mp.get(A[i]) != null ) mp.put(A[i], mp.get(A[i]) + 1 ); else mp.put(A[i], 1 ); } // Check any unique element is present // In array or any element // Which is not array; for ( int i = 0 ; i <= N; i++) { if (mp.get(i) == null ) { System.out.println(i); break ; } if (mp.get(i) == 1 ) { status = false ; break ; } } if (status == true ) { // Sort the array Arrays.sort(A); int A1[] = new int [N / 2 ]; int A2[] = new int [N / 2 ]; // Push all elements at even index // in first array and at odd index // into another array for ( int i = 0 ; i < N / 2 ; i++) { A1[i] = A[ 2 * i]; A2[i] = A[ 2 * i + 1 ]; } // Print both the arrays for ( int i = 0 ; i < N / 2 ; i++) { System.out.print(A1[i] + " " ); } System.out.println(); for ( int i = 0 ; i < N / 2 ; i++) { System.out.print(A2[i] + " " ); } } // If not possible to divide // into two array, print -1 else System.out.print(- 1 ); } public static void main(String[] args) { int N = 6 ; int arr[] = { 1 , 6 , 2 , 3 , 5 , 2 }; // Function call MEX_arr(arr, N); } } // This code is contributed by Rohit Pradhan. |
Python3
# python3 code to implement the above approach: # Function to find the # Least common missing no. def MEX_arr(A, N): mp = {} status = True # Push all array elements # Into unordered_map for i in range ( 0 , N): mp[A[i]] = mp[A[i]] + 1 if A[i] in mp else 1 # Check any unique element is present # In array or any element # Which is not array; for i in range ( 0 , N + 1 ): if ( not i in mp): print (i) break elif (mp[i] = = 1 ): status = False break if (status = = True ): # Sort the array A.sort() A1, A2 = [ 0 for _ in range (N / / 2 )], [ 0 for _ in range (N / / 2 )] # Push all elements at even index # in first array and at odd index # into another array for i in range ( 0 , N / / 2 ): A1[i] = A[ 2 * i] A2[i] = A[ 2 * i + 1 ] # Print both the arrays for i in range ( 0 , N / / 2 ): print (A1[i], end = " " ) print () for i in range ( 0 , N / / 2 ): print (A2[i], end = " " ) # If not possible to divide # into two array, print -1 else : print ( - 1 ) # Driver code if __name__ = = "__main__" : N = 6 arr = [ 1 , 6 , 2 , 3 , 5 , 2 ] # unordered_map<int, int> mp; # Function call MEX_arr(arr, N) # This code is contributed by rakeshsahni |
C#
// C# code to implement the above approach: using System; using System.Collections.Generic; class GFG { // Function to find the // Least common missing no. static void MEX_arr( int []A, int N) { Dictionary< int , int > mp = new Dictionary< int , int >(); bool status = true ; // Push all array elements // Into unordered_map for ( int i = 0; i < N; i++) { if (mp.ContainsKey(A[i])) { mp[A[i]] = mp[A[i]] + 1; } else { mp.Add(A[i], 1); } } // Check any unique element is present // In array or any element // Which is not array; for ( int i = 0; i <= N; i++) { if (!mp.ContainsKey(i)) { Console.WriteLine(i); break ; } if (mp[i] == 1) { status = false ; break ; } } if (status == true ) { // Sort the array Array.Sort(A); int []A1 = new int [N / 2]; int []A2 = new int [N / 2]; // Push all elements at even index // in first array and at odd index // into another array for ( int i = 0; i < N / 2; i++) { A1[i] = A[2 * i]; A2[i] = A[2 * i + 1]; } // Print both the arrays for ( int i = 0; i < N / 2; i++) { Console.Write(A1[i] + " " ); } Console.WriteLine(); for ( int i = 0; i < N / 2; i++) { Console.Write(A2[i] + " " ); } } // If not possible to divide // into two array, print -1 else Console.Write(-1); } // Driver code public static void Main() { int N = 6; int []arr = { 1, 6, 2, 3, 5, 2 }; // Function call MEX_arr(arr, N); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the // Least common missing no. function MEX_arr(A, N) { let mp = new Map(); var status = true ; // Push all array elements // Into unordered_map for (let i = 0; i < N; i++) { if (!mp.has(A[i])) { mp.set(A[i], 1); } else { mp.set(A[i], mp.get(A[i]) + 1) } } // Check any unique element is present // In array or any element // Which is not array; for (let i = 0; i <= N; i++) { if (!mp.has(i)) { document.write(i + '<br>' ) break ; } else if (mp.get(i) == 1) { status = false ; break ; } } if (status == true ) { // Sort the array A.sort( function (a, b) { return a - b }) let A1 = new Array(Math.floor(N / 2)); let A2 = new Array(Math.floor(N / 2)); // Push all elements at even index // in first array and at odd index // into another array for (let i = 0; i < Math.floor(N / 2); i++) { A1[i] = A[2 * i]; A2[i] = A[2 * i + 1]; } // Print both the arrays for (let i = 0; i < N / 2; i++) { document.write(A1[i] + ' ' ) } document.write( '<br>' ) for (let i = 0; i < N / 2; i++) { document.write(A2[i] + ' ' ) } } // If not possible to divide // into two array, print -1 else document.write(-1) } // Driver code let N = 6; let arr = [1, 6, 2, 3, 5, 2]; // Function call MEX_arr(arr, N); // This code is contributed by Potta Lokesh </script> |
0 1 2 5 2 3 6
Time Complexity: O(N * log(N))
Auxiliary space: O(N)
Contact Us