Given an array arr[] of size N, the task is to rearrange the array elements such that the sum of MEX of all prefix arrays is the maximum possible.
Note: MEX of a sequence is the minimum non-negative number not present in the sequence.
Examples:
Input: arr[] = {2, 0, 1}
Output: 0, 1, 2
Explanation:
Sum of MEX of all prefix arrays of all possible permutations of the given array:
arr[] = {0, 1, 2}, Mex(0) + Mex(0, 1) + Mex(0, 1, 2) = 1 + 2 + 3 = 6
arr[] = {1, 0, 2}, Mex(1) + Mex(1, 0) + Mex(1, 0, 2) = 0 + 2 + 3 = 5
arr[] = {2, 0, 1}, Mex(2) + Mex(2, 0) + Mex(2, 0, 1) = 0 + 1 + 3 = 4
arr[] = {0, 2, 1}, Mex(0) + Mex(0, 2) + Mex(0, 2, 1) = 1 + 1 + 3 = 5
arr[] = {1, 2, 0}, Mex(1) + Mex(1, 2) + Mex(1, 2, 0) = 0 + 0 + 3 = 3
arr[] = {2, 1, 0}, Mex(2) + Mex(2, 1) + Mex(2, 1, 0) = 0 + 0 + 3 = 3
Hence, the maximum sum possible is 6.Input: arr[] = {1, 0, 0}
Output: 0, 1, 0
Explanation:
Sum of MEX of all prefix arrays of all possible permutations of the given array:
arr[]={1, 0, 0}, Mex(1) + Mex(1, 0) + Mex(1, 0, 0) = 0 + 2 + 2 = 4
arr[]={0, 1, 0}, Mex(0) + Mex(0, 1) + Mex(0, 1, 0) = 1 + 2 + 2 = 5
arr[]={0, 0, 1}, Mex(0) + Mex(0, 0) + Mex(0, 0, 1) = 1 + 1 + 2 = 4
Hence, the maximum value is 5 for the arrangement, arr[]={0, 1, 0}.
Naive Approach: The simplest approach is to generate all possible permutations of the given array arr[] and then for each permutation, find the value of MEX of all the prefix arrays, while keeping track of the overall maximum value. After iterating over all possible permutations, print the permutation having the largest value.
Time Complexity: O(N2 * N!)
Auxiliary Space: O(N)
Efficient Approach: The optimal idea is based on the observation that the sum of MEX of prefix arrays will be maximum when all the distinct elements are arranged in increasing order and the duplicates are present at the end of the array.
Follow the steps below to solve the problem:
- Initialize a vector of integers, say ans, to store the required arrangement.
- Sort the array arr[] in increasing order.
- Traverse the array arr[] and push all distinct elements into the array ans[].
- Again traverse the array arr[] and push all the remaining duplicate elements into the array ans[].
- After completing the above steps, print the array ans[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of// MEX of prefix arrays for any// arrangement of the given arrayvoid maximumMex(int arr[], int N){ // Stores the final arrangement vector<int> ans; // Sort the array in increasing order sort(arr, arr + N); // Iterate over the array arr[] for (int i = 0; i < N; i++) { if (i == 0 || arr[i] != arr[i - 1]) ans.push_back(arr[i]); } // Iterate over the array, arr[] // and push the remaining occurrences // of the elements into ans[] for (int i = 0; i < N; i++) { if (i > 0 && arr[i] == arr[i - 1]) ans.push_back(arr[i]); } // Print the array, ans[] for (int i = 0; i < N; i++) cout << ans[i] << " ";}// Driver Codeint main(){ // Given array int arr[] = { 1, 0, 0 }; // Store the size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function Call maximumMex(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays; class GFG{ // Function to find the maximum sum of// MEX of prefix arrays for any// arrangement of the given arraystatic void maximumMex(int arr[], int N){ // Stores the final arrangement int ans[] = new int[2 * N]; // Sort the array in increasing order Arrays.sort(ans); int j = 0; // Iterate over the array arr[] for(int i = 0; i < N; i++) { if (i == 0 || arr[i] != arr[i - 1]) { j += 1; ans[j] = arr[i]; } } // Iterate over the array, arr[] // and push the remaining occurrences // of the elements into ans[] for(int i = 0; i < N; i++) { if (i > 0 && arr[i] == arr[i - 1]) { j += 1; ans[j] = arr[i]; } } // Print the array, ans[] for(int i = 0; i < N; i++) System.out.print(ans[i] + " ");}// Driver Codepublic static void main (String[] args){ // Given array int arr[] = { 1, 0, 0 }; // Store the size of the array int N = arr.length; // Function Call maximumMex(arr, N);}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find the maximum sum of# MEX of prefix arrays for any# arrangement of the given arraydef maximumMex(arr, N): # Stores the final arrangement ans = [] # Sort the array in increasing order arr = sorted(arr) # Iterate over the array arr[] for i in range(N): if (i == 0 or arr[i] != arr[i - 1]): ans.append(arr[i]) # Iterate over the array, arr[] # and push the remaining occurrences # of the elements into ans[] for i in range(N): if (i > 0 and arr[i] == arr[i - 1]): ans.append(arr[i]) # Print the array, ans[] for i in range(N): print(ans[i], end = " ")# Driver Codeif __name__ == '__main__': # Given array arr = [1, 0, 0 ] # Store the size of the array N = len(arr) # Function Call maximumMex(arr, N)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum sum of// MEX of prefix arrays for any// arrangement of the given arraystatic void maximumMex(int []arr, int N){ // Stores the final arrangement int []ans = new int[2 * N]; // Sort the array in increasing order Array.Sort(ans); int j = 0; // Iterate over the array arr[] for(int i = 0; i < N; i++) { if (i == 0 || arr[i] != arr[i - 1]) { j += 1; ans[j] = arr[i]; } } // Iterate over the array, arr[] // and push the remaining occurrences // of the elements into ans[] for(int i = 0; i < N; i++) { if (i > 0 && arr[i] == arr[i - 1]) { j += 1; ans[j] = arr[i]; } } // Print the array, ans[] for(int i = 0; i < N; i++) Console.Write(ans[i] + " ");}// Driver Codepublic static void Main (string[] args){ // Given array int []arr = { 1, 0, 0 }; // Store the size of the array int N = arr.Length; // Function Call maximumMex(arr, N);}}// This code is contributed by AnkThon |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum sum of// MEX of prefix arrays for any// arrangement of the given arrayfunction maximumMex(arr, N){ // Stores the final arrangement var ans = []; // Sort the array in increasing order arr.sort(); var i; // Iterate over the array arr[] for (i = 0; i < N; i++) { if (i == 0 || arr[i] != arr[i - 1]) ans.push(arr[i]); } // Iterate over the array, arr[] // and push the remaining occurrences // of the elements into ans[] for (i = 0; i < N; i++) { if (i > 0 && arr[i] == arr[i - 1]) ans.push(arr[i]); } // Print the array, ans[] for (i = 0; i < N; i++) document.write(ans[i] + " ");}// Driver Code // Given array var arr = [1, 0, 0]; // Store the size of the array var N = arr.length; // Function Call maximumMex(arr, N);</script> |
0 1 0
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
