Reconstructing the Array with Maximum Possible Sum by Given Operations
Consider an array A[] of length N. Suppose, you can create obtain B[] from A[] using below steps:
- Iterate N/2 times on A and follow below the step below:
- Insert (Ai + Ai+(N/2)) and |Ai – Ai+(N/2)| into B[]
- After that rearrange B[] in any random order.
You are given B[], the task is to reconstructing any A[] if exists such that B[] can be obtained using above operations. If it is, then sum of A[] must be maximum possible else output -1.
Examples:
Input: N = 6, B[] = {4, 2, 8, 2, 10, 4}
Output: A[] = {7, 5, 3, 3, 3, 1}
Explanation: Considered that A[] is {7, 5, 3, 3, 3, 1} and B[] empty. Then (N=6)/2 = 3 iterations will be as follows:
- First Iteration (i = 1): (A1 + A1+(6/2)) and |A1 – A1+(6/2)| and (A1 + A1+(6/2)) and |A1 – A1+(6/2)| are 7+3 = 10 and |7-3| = 4 respectively. Updated B[] = {10, 4}
- Second Iteration (i = 2): (A2 + A2+(6/2)) and |A2 – A2+(6/2)| and (A2 + A2+(6/2)) and |A2 – A2+(6/2)| are 5+3 = 8 and ∣5−3∣= 2 respectively. Updated B[] = {10, 4, 8, 2}
- Third Iteration (i = 3): (A3 + A3+(6/2)) and |A3 – A3+(6/2)| and (A3 + A3+(6/2)) and |A3 – A3+(6/2)| are 3+1 = 4 and ∣3−1∣ = 2 respectively. Updated B[] = {10, 4, 8, 2, 4, 2}
It can be verified that obtained updated B[] = {10, 4, 8, 2, 4, 2} is an arrangement of input B[] = {4, 2, 8, 2, 10, 4}. Thus, B[] can be achieved by A[] using given operation. It can also verified that the sum of A[] among all possible such arrays is maximum possible, which is 22 (7+5+3+3+3+1).Input: N = 2, B[] = {2, 3}
Output: -1
Explanation: It can be verified that no such A[] exists, by which we can obtain B[] using given operation.
Approach:
Firstly, we will check if the sum of B[] is even or not, the reason for checking is this we can confirm that whether such an array A[] really exist or not.
After this break the B[] in to arrays one with all even number and one with odd number. Next the two elements of A[] can be computed by basic math and we need max sum of A[]. Therefore, what we would do is this:
Greatest(EVEN) + Smallest(EVEN) and Greatest(EVEN) – Greatest(EVEN)
Same we will do with the subarray containing odd elements.
Step-by-step approach:
- Initialize two
arrays
EV[]
for even numbers andOD[]
for odd numbers. - Iterate over the
B[]
and add even numbers toEV[]
and odd numbers toOD[]
. - Check if the size of both
EV[]
andOD[]
is even. If not, output-1
. - Sort both
EV[]
andOD[]
. - Initialize an array let say
A[]
of sizeN
to store the result. - Use two pointers
p
andq
to iterate overEV[]
andOD[]
from the smallest to the largest and from the largest to the smallest, respectively. - Calculate the sum
X
and the differenceY
for each pair of elements fromEV[]
andOD[]
. - Store the average of the sum in the first half of array
A[]
and the average of the difference in the second half of arrayA[]
. - Continue this process until all elements are processed.
- Print the elements of array
A[]
.
Below is the implementation of the above approach:
C++
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to output A[], if it exists void FindA( int N, vector< int >& B) { vector< int > A(N); vector< int > EV; // Vector to store even numbers vector< int > OD; // Vector to store odd numbers for ( int i = 0; i < N; i++) { if (B[i] % 2 == 0) { EV.push_back(B[i]); // Add even numbers to EV } else { OD.push_back(B[i]); // Add odd numbers to OD } } // Check if the number of even and odd numbers are even if (EV.size() % 2 != 0 || OD.size() % 2 != 0) { cout << "-1" << endl; } else { sort(EV.begin(), EV.end()); // Sort the array of even numbers sort(OD.begin(), OD.end()); // Sort the array of odd numbers int n = EV.size(); int p = 0; int q = n - 1; int j = 0; while (p < q) { int a = EV[q]; // Get the greatest even number int b = EV[p]; // Get the smallest even number int X = a + b; // Sum of the greatest and smallest even numbers int Y = a - b; // Difference of the greatest and smallest even numbers A[j] = X / 2; // Store the average of the sum in the first half of array A A[j + (N / 2)] = Y / 2; // Store the average of the difference in the // second half of array j++; q--; p++; } n = OD.size(); p = 0; q = n - 1; while (p < q) { int a = OD[q]; // Get the greatest odd number int b = OD[p]; // Get the smallest odd number int X = a + b; // Sum of the greatest and smallest odd numbers int Y = a - b; // Difference of the greatest and smallest odd numbers A[j] = X / 2; // Store the average of the sum in the first half of array A A[j + (N / 2)] = Y / 2; // Store the average of the difference // in the second half of array j++; q--; p++; } for ( int i : A) { cout << i << " " ; } cout << endl; } } // Driver Code int main() { // Input int N = 6; vector< int > B = {4, 2, 8, 2, 10, 4}; // Function call FindA(N, B); return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; // Driver Class class Main { public static void main(String[] args) throws java.lang.Exception { // Input int N = 6 ; int [] B = { 4 , 2 , 8 , 2 , 10 , 4 }; // Function_call FindA(N, B); } // method to output A[], If it exists public static void FindA( int N, int [] B) { int [] A = new int [N]; ArrayList<Integer> EV = new ArrayList<Integer>(); // Array to store // even numbers ArrayList<Integer> OD = new ArrayList<Integer>(); // Array to store // odd numbers for ( int i = 0 ; i < N; i++) { if (B[i] % 2 == 0 ) { EV.add(B[i]); // Add even numbers to EV } else { OD.add(B[i]); // Add odd numbers to OD } } // Check if the number of even and odd numbers are // even if ((EV.size()) % 2 != 0 || (OD.size()) % 2 != 0 ) { System.out.println( "-1" ); } else { Collections.sort( EV); // Sort the array of even numbers Collections.sort( OD); // Sort the array of odd numbers int n = EV.size(); int p = 0 ; int q = n - 1 ; int j = 0 ; while (p < q) { int a = EV.get( q); // Get the greatest even number int b = EV.get( p); // Get the smallest even number int X = (a + b); // Sum of the greatest and // smallest even numbers int Y = (a - b); // Difference of the greatest // and smallest even numbers A[j] = X / 2 ; // Store the average of the sum // in the first half of array A A[j + (N / 2 )] = Y / 2 ; // Store the average of the // difference in the second // half of array A j++; q--; p++; } n = OD.size(); p = 0 ; q = n - 1 ; while (p < q) { int a = OD.get( q); // Get the greatest odd number int b = OD.get( p); // Get the smallest odd number int X = (a + b); // Sum of the greatest and // smallest odd numbers int Y = (a - b); // Difference of the greatest // and smallest odd numbers A[j] = X / 2 ; // Store the average of the sum // in the first half of array A A[j + (N / 2 )] = Y / 2 ; // Store the average of the // difference in the second // half of array A j++; q--; p++; } for ( int i : A) { System.out.print(i + " " ); } System.out.println(); } } } |
Python3
def GFG(N, B): A = [ 0 ] * N EV = [] OD = [] # Separate even and odd numbers for i in range (N): if B[i] % 2 = = 0 : EV.append(B[i]) else : OD.append(B[i]) # Check if the number of even and odd numbers is even if len (EV) % 2 ! = 0 or len (OD) % 2 ! = 0 : print ( "-1" ) else : EV.sort() # Sort the array of even numbers OD.sort() # Sort the array of odd numbers n = len (EV) p = 0 q = n - 1 j = 0 # Process even numbers while p < q: a = EV[q] b = EV[p] X = a + b Y = a - b A[j] = X / / 2 # Store the average of the sum in the first half of array A A[j + N / / 2 ] = Y / / 2 # Store the average of the difference in the second half of array A j + = 1 q - = 1 p + = 1 n = len (OD) p = 0 q = n - 1 # Process odd numbers while p < q: a = OD[q] b = OD[p] X = a + b Y = a - b A[j] = X / / 2 A[j + N / / 2 ] = Y / / 2 j + = 1 q - = 1 p + = 1 # Print the result print ( " " .join( map ( str , A))) # Driver Code def main(): # Input N = 6 B = [ 4 , 2 , 8 , 2 , 10 , 4 ] # Function call GFG(N, B) if __name__ = = "__main__" : main() |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to output A[], if it exists static void FindA( int N, List< int > B) { List< int > A = new List< int >( new int [N]); List< int > EV = new List< int >(); // List to store even numbers List< int > OD = new List< int >(); // List to store odd numbers // Separate even and odd numbers foreach ( int num in B) { if (num % 2 == 0) { EV.Add(num); // Add even numbers to EV } else { OD.Add(num); // Add odd numbers to OD } } // Check if the number of even and odd numbers are even if (EV.Count % 2 != 0 || OD.Count % 2 != 0) { Console.WriteLine( "-1" ); } else { EV.Sort(); // Sort the list of even numbers OD.Sort(); // Sort the list of odd numbers int n = EV.Count; int p = 0; int q = n - 1; int j = 0; // Merge even numbers while (p < q) { int a = EV[q]; // Get the greatest even number int b = EV[p]; // Get the smallest even number int X = a + b; // Sum of the greatest and smallest even numbers int Y = a - b; // Difference of the greatest and smallest even numbers A[j] = X / 2; // Store the average of the sum in the first half of array A A[j + (N / 2)] = Y / 2; // Store the average of the difference in the second half of array j++; q--; p++; } n = OD.Count; p = 0; q = n - 1; // Merge odd numbers while (p < q) { int a = OD[q]; // Get the greatest odd number int b = OD[p]; // Get the smallest odd number int X = a + b; // Sum of the greatest and smallest odd numbers int Y = a - b; // Difference of the greatest and smallest odd numbers A[j] = X / 2; // Store the average of the sum in the first half of array A A[j + (N / 2)] = Y / 2; // Store the average of the difference in the second half of array j++; q--; p++; } // Output the resulting array A foreach ( int i in A) { Console.Write(i + " " ); } Console.WriteLine(); } } // Driver Code static void Main() { // Input int N = 6; List< int > B = new List< int > { 4, 2, 8, 2, 10, 4 }; // Function call FindA(N, B); } } |
Javascript
function GFG(N, B) { let A = new Array(N); let EV = []; let OD = []; // Separate even and odd numbers for (let i = 0; i < N; i++) { if (B[i] % 2 === 0) { EV.push(B[i]); } else { OD.push(B[i]); } } // Check if the number of the even and odd numbers are even if (EV.length % 2 !== 0 || OD.length % 2 !== 0) { console.log( "-1" ); } else { EV.sort((a, b) => a - b); // Sort the array of the even numbers OD.sort((a, b) => a - b); // Sort the array of odd numbers let n = EV.length; let p = 0; let q = n - 1; let j = 0; // Process even numbers while (p < q) { let a = EV[q]; let b = EV[p]; let X = a + b; let Y = a - b; A[j] = X / 2; // Store the average of the sum in the first half of array A A[j + N / 2] = Y / 2; // Store the average of the difference in the second half of array A j++; q--; p++; } n = OD.length; p = 0; q = n - 1; // Process odd numbers while (p < q) { let a = OD[q]; let b = OD[p]; let X = a + b; let Y = a - b; A[j] = X / 2; A[j + N / 2] = Y / 2; j++; q--; p++; } // Print the result console.log(A.join( " " )); } } // Driver Code function main() { // Input let N = 6; let B = [4, 2, 8, 2, 10, 4]; // Function call GFG(N, B); } main(); |
6 5 4 4 3 0
Time Complexity: O(NLogN), As sorting is performed.
Auxiliary Space: O(N), As ArrayLists EV and OD of length N are used.