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.