Reorder an array such that sum of left half is not equal to sum of right half

Given a an array of even size N. The task is to find that is it possible to reorder it in such way so that the sum of left half is not equal to the sum of right half.
Print -1 if not possible else print the required array.

Examples:

Input:
arr = {1, 2, 2, 1, 3, 1} 
Output:
1 1 1 2 2 3 
Explanation:
Sum of left half = 1 + 2 + 2 = 5 
Sum of right half = 2 + 2 + 3 = 7 
Both half are not equal. 

Input:
arr = {1, 1} 
Output:
-1

Approach:
If all elements in the array are equal, then there is no solution.
Otherwise, we can sort the array. The sum of the second half will always be greater than that of the first half since elements are sorted.

Below is the implementation of the above approach:

// C++ implementation to print the required array
#include <bits/stdc++.h> 
using namespace std; 

// Function to print the required array
void printArr(int A[], int n) 
{ 
    // Sort the array       
    sort(A, A + n);
    
    // If all elements are equal, then it's not possible
    if (A[0] == A[n - 1])
        cout << -1;
    // Printing the required array
    else
    {
        for (int i = 0; i < n; i++)
            cout << A[i] << " ";
    }
} 

// Driver code 
int main() 
{       
    int arr[] = {1, 2, 2, 1, 3, 1};
    int n = 6;
    printArr(arr, n); 
    return 0; 
}

Output:

1 1 1 2 2 3

Time complexity: O(n logn)
Space complexity: O(n)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.