Generate an Array by given Array such that prefix sums is maximum
Given an array A[] and the operation of swapping two elements if their sum is even, find a resulting array B[] such that all prefix sums of B[] are maximum among all possible arrays that can be obtained by applying the given operation any number of times on A[].
Examples:
Input: A[] = {1, 5, 7}
Output: B[] = {7, 5, 1}
Explanation:
- Operation 1: A2 + A3 = 5 + 7 = 12, Which is even therefore swap both. Then, A[] = {1, 7, 5}
- Operation 2: A1 + A2 = 1 + 7 = 8, Which is even therefore swap both. Then, A[] = {7, 1, 5}
- Operation 3: A2 + A3 = 1 + 5 = 6, Which is even therefore swap both. Then, A[] = {7, 5, 1}
Prefix sums array of B[] will be: {7, 12, 13}. Which is maximum possible among all the arrays that can be generated by applying given operations on A[].
Input: A[] = {2, 6, 1, 3}
Output: B[] = {6, 2, 3, 1}
Explanation: It can be verified that the output array will have the maximum possible prefix sums.
Approach: To solve the problem follow the below idea:
The problem is based on Greedy logic for maximizing the prefix sums. The problem can be solved using Two-Pointer technique. For maximizing prefix sums, We have to shift max element at leftmost possible index. But it is only possible, When adjacent elements have optimal parity. We know that, Even + Even = Even and Odd + Odd = Even. So, We come to know that for swapping elements parity of them should be same.
Illustration:
Now let us understand it with an example:
- Considered A[] = {1, 5, 7}, We can swap 7 to first index by swapping it 2 times and 5 at second index by swapping 5 once(See explanation of first test case). Then A[] = {7, 5, 1}. We can easily swap the elements under same parity. Formally, here all the elements are odd and can be placed at any index, Because all follows the condition of even sum. Also It should be noted that we sort the sub-array of same parity in descending order, So that prefix sum can be maximized.
- Now, considered A[] = {4, 2, 1, 5}, There are two sub-arrays of different parity, {4, 2} ans {1, 5} having even and odd parity respectively. For maximizing sum, We will arrange these sub-arrays in descending order. Then A[] = {4, 2, 5, 1}. It can be verified that array formed by this approach will always have maximum prefix sums among all the arrays that can be generated by initial A[].
Below are the steps for the above approach:
- Initialize a variable leftEnd = 0.
- Initialize an ArrayList of integers say the list.
- Run a loop till leftEnd < A.length.
- Determine the parity of the first element of the sub-array starting from index leftEnd. If the first element is even, the parity is 0, else, it is 1.
- Initialize a variable say rightEnd = leftEnd.
- Add the first element to the list.
- Run another loop till rightEnd < (A.length – 1) && A[rightEnd + 1] % 2 == parity.
- Increment the value of rightEnd and add the next element to the list.
- Sort the ArrayList list in reverse order.
- Initialize a variable counter = 0.
- Run a loop till i <= (leftEnd + list.size() – 1) and iterate from leftEnd to (leftEnd + list.size() – 1).
- Set the value of A[i] to the value at the index counter of the ArrayList list, and increment the value of the counter.
- Clear the ArrayList list.
- Update the value of leftEnd = rightEnd + 1.
- Print the array A[].
Below is the code to implement the approach:
C++
#include <iostream> #include <vector> #include <algorithm> void maxPrefix(std::vector< int >& A) { int leftEnd = 0; std::vector< int > lst; while (leftEnd < A.size()) { int parity = (A[leftEnd] % 2 == 0) ? 0 : 1; int rightEnd = leftEnd; lst.push_back(A[leftEnd]); while (rightEnd < A.size() - 1 && A[rightEnd + 1] % 2 == parity) { rightEnd++; lst.push_back(A[rightEnd]); } std::sort(lst.rbegin(), lst.rend()); int counter = 0; for ( int i = leftEnd; i < leftEnd + lst.size(); i++) { A[i] = lst[counter]; counter++; } lst.clear(); leftEnd = rightEnd + 1; } // Printing A[] std::cout << "[" ; for ( int i = 0; i < A.size(); i++) { std::cout << A[i]; if (i != A.size() - 1) { std::cout << ", " ; } } std::cout << "]" << std::endl; } int main() { std::vector< int > A = {1, 5, 7}; maxPrefix(A); return 0; } |
Java
// Java code to implement the approach import java.util.*; public class Main { // Driver Function public static void main(String[] args) { // Input A[] int A[] = { 1 , 5 , 7 }; // Function call MaxPrefix(A); } // Method for implementing the approach static void MaxPrefix( int [] A) { // 1st pointer int leftEnd = 0 ; // ArrayList for temporary storing // same parity sub-arrays ArrayList<Integer> list = new ArrayList<>(); while (leftEnd < A.length) { // Variable to hold parity of // current sub-array // For odd parity = 1, // for Even parity = 0 int parity = A[leftEnd] % 2 == 0 ? 0 : 1 ; // 2nd pointer int rightEnd = leftEnd; list.add(A[leftEnd]); while (rightEnd < (A.length - 1 ) && A[rightEnd + 1 ] % 2 == parity) { rightEnd++; list.add(A[rightEnd]); } // Sorting the list in // reverse order list.sort(Collections.reverseOrder()); // Counter varuble for // iterating from // starting on ArrayList int counter = 0 ; // Lop for initializing // elements from list to A[] for ( int i = leftEnd; i <= (leftEnd + list.size() - 1 ); i++) { A[i] = list.get(counter); counter++; } // Clearing all the elements // from List list.clear(); // Updating the value of // 1st pointer leftEnd = rightEnd + 1 ; } // Printing A[] System.out.println(Arrays.toString(A)); } } |
Python3
# python code to implement the approach def maxPrefix(A): # 1st pointer leftEnd = 0 # List for temporary storing same parity sub-arrays lst = [] while leftEnd < len (A): # Variable to hold parity of current sub-array # For odd parity = 1, for even parity = 0 parity = 0 if A[leftEnd] % 2 = = 0 else 1 # 2nd pointer rightEnd = leftEnd lst.append(A[leftEnd]) while (rightEnd < len (A) - 1 ) and (A[rightEnd + 1 ] % 2 = = parity): rightEnd + = 1 lst.append(A[rightEnd]) # Sorting the list in reverse order lst.sort(reverse = True ) # Counter variable for iterating from starting on the list counter = 0 # Loop for initializing elements from the list to A[] for i in range (leftEnd, leftEnd + len (lst)): A[i] = lst[counter] counter + = 1 # Clearing all the elements from the list lst.clear() # Updating the value of the 1st pointer leftEnd = rightEnd + 1 # Printing A[] print (A) # Driver code A = [ 1 , 5 , 7 ] maxPrefix(A) |
C#
using System; using System.Collections.Generic; public class Program { // Driver Function public static void Main( string [] args) { // Input A[] int [] A = { 1, 5, 7 }; // Function call MaxPrefix(A); } // Method for implementing the approach static void MaxPrefix( int [] A) { // 1st pointer int leftEnd = 0; // List for temporary storing // same parity sub-arrays List< int > list = new List< int >(); while (leftEnd < A.Length) { // Variable to hold parity of // current sub-array // For odd parity = 1, // for Even parity = 0 int parity = A[leftEnd] % 2 == 0 ? 0 : 1; // 2nd pointer int rightEnd = leftEnd; list.Add(A[leftEnd]); while (rightEnd < (A.Length - 1) && A[rightEnd + 1] % 2 == parity) { rightEnd++; list.Add(A[rightEnd]); } // Sorting the list in // reverse order list.Sort(); list.Reverse(); // Counter variable for // iterating from // starting on List int counter = 0; // Loop for initializing // elements from list to A[] for ( int i = leftEnd; i <= (leftEnd + list.Count - 1); i++) { A[i] = list[counter]; counter++; } // Clearing all the elements // from List list.Clear(); // Updating the value of // 1st pointer leftEnd = rightEnd + 1; } // Printing A[] Console.WriteLine( string .Join( ", " , A)); } } |
Javascript
// Method for implementing the approach function maxPrefix(A) { // 1st pointer let leftEnd = 0; // ArrayList for temporary storing // same parity sub-arrays let lst = []; while (leftEnd < A.length) { // Variable to hold parity of // current sub-array // For odd parity = 1, // for Even parity = 0 let parity = (A[leftEnd] % 2 === 0) ? 0 : 1; // 2nd pointer let rightEnd = leftEnd; lst.push(A[leftEnd]); while (rightEnd < A.length - 1 && A[rightEnd + 1] % 2 === parity) { rightEnd++; lst.push(A[rightEnd]); } // Sorting the list in // reverse order lst.sort((a, b) => b - a); // Counter varuble for // iterating from // starting on ArrayList let counter = 0; // Lop for initializing // elements from list to A[] for (let i = leftEnd; i < leftEnd + lst.length; i++) { A[i] = lst[counter]; counter++; } // Clearing all the elements // from List lst = []; // Updating the value of // 1st pointer leftEnd = rightEnd + 1; } console.log( "[" , A.join( ", " ), "]" ); } // Driver code let A = [1, 5, 7]; maxPrefix(A); |
[7, 5, 1]
Time Complexity: O(N2)
Auxiliary Space: O(1)
Contact Us