Given an array arr[] consisting of N integers, the task is to rearrange the array such that sum of all subarrays starting from the first index of the array is non-zero. If it is not possible to generate such arrangement, then print “-1”.
Examples:
Input: arr[] = {-1, 1, -2, 3}
Output: {-1, -2, 1, 3}
Explanation: One of the possible rearrangement is {-1, -2, 1, 3}.
Subarrays starting from index 0 are {-1}, {-1, -2}, {-1, -2, 1} and {-1, -2, 1, 3}. None of the above subarrays have sum 0.Input: arr[] = {0, 0, 0, 0}
Output: -1
Approach: Desired array can be obtained from the given array if it is in any of the following two configurations:
- If the given array is sorted in ascending order, the first subarray with sum zero can be handled by replacing the last element of the subarray with an element greater than it.
- Similarly, in arrays sorted in descending order, by replacing the first element of the subarray with sum zero with an element smaller than it to ensure that the sum thereafter is negative.
Follow the steps below to solve the problem:
- When array is sorted in ascending order:
- Sort the array arr[] in ascending order and find the sum of the first i elements of the array (0 ? i ? N).
- When a zero-sum encountered, replace the element nullifying the prefix sum (i.e., ith element) with the largest element of the array:
- If the largest element of the array is equal to the integer causing nullification, then move to the second configuration.
- If the largest element is greater than the problematic element, this replacement ensures positive-sum instead of zero.
- When array is sorted in descending order:
- Sort the array arr[] in descending order and start finding the sum of the last i elements of the array (0 ? i ? N).
- When zero-sum is encountered, replace the element nullifying the prefix sum (i.e. ith element) with the smallest element of the array:
- If the smallest element of the array is equal to the integer causing nullification, then it’s not possible to rearrange the array arr[].
- If the smallest element is smaller than the problematic element, this replacement ensures a negative-sum instead of zero.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to rearrange the array such// that sum of all elements of subarrays// from the 1st index is non-zerovoid rearrangeArray(int a[], int N){ // Initialize sum of subarrays int sum = 0; // Sum of all elements of array for (int i = 0; i < N; i++) { sum += a[i]; } // If sum is 0, the required // array could never be formed if (sum == 0) { cout << "-1"; return; } // If sum is non zero, array // might be formed sum = 0; int b = 0; // Sort array in ascending order sort(a, a + N); for (int i = 0; i < N; i++) { sum += a[i]; // When current subarray sum // becomes 0 replace it with // the largest element if (sum == 0) { if (a[i] != a[N - 1]) { sum -= a[i]; // Swap Operation swap(a[i], a[N - 1]); sum += a[i]; } // If largest element is same // as element to be replaced, // then rearrangement impossible else { b = 1; break; } } } // If b = 1, then rearrangement // is not possible. Hence check // with reverse configuration if (b == 1) { b = 0; sum = 0; // Sort array in descending order sort(a, a + N, greater<int>()); // When current subarray sum // becomes 0 replace it with // the smallest element for (int i = N - 1; i >= 0; i--) { sum += a[i]; if (sum == 0) { if (a[i] != a[0]) { sum -= a[i]; // Swap Operation swap(a[i], a[0]); sum += a[i]; } // If smallest element is same // as element to be replaced, // then rearrangement impossible else { b = 1; break; } } } } // If neither of the configurations // worked then print "-1" if (b == 1) { cout << "-1"; return; } // Otherwise, print the formed // rearrangement for (int i = 0; i < N; i++) { cout << a[i] << " "; }}// Driver Codeint main(){ // Given array int arr[] = { 1, -1, 2, 4, 0 }; // Size of array int N = sizeof(arr) / sizeof(arr[0]); // Function Call rearrangeArray(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;import java.util.Arrays; import java.util.Collections; class GFG{// Function to rearrange the array such// that sum of all elements of subarrays// from the 1st index is non-zerostatic void rearrangeArray(int a[], int N){ // Initialize sum of subarrays int sum = 0; // Sum of all elements of array for(int i = 0; i < N; i++) { sum += a[i]; } // If sum is 0, the required // array could never be formed if (sum == 0) { System.out.print("-1"); return; } // If sum is non zero, array // might be formed sum = 0; int b = 0; // Sort array in ascending order Arrays.sort(a); for(int i = 0; i < N; i++) { sum += a[i]; // When current subarray sum // becomes 0 replace it with // the largest element if (sum == 0) { if (a[i] != a[N - 1]) { sum -= a[i]; // Swap Operation int temp = a[i]; a[i] = a[N - 1]; a[N - 1] = temp; sum += a[i]; } // If largest element is same // as element to be replaced, // then rearrangement impossible else { b = 1; break; } } } // If b = 1, then rearrangement // is not possible. Hence check // with reverse configuration if (b == 1) { b = 0; sum = 0; // Sort array in descending order Arrays.sort(a); // When current subarray sum // becomes 0 replace it with // the smallest element for(int i = N - 1; i >= 0; i--) { sum += a[i]; if (sum == 0) { if (a[i] != a[0]) { sum -= a[i]; // Swap Operation int temp = a[i]; a[i] = a[0]; a[0] = temp; sum += a[i]; } // If smallest element is same // as element to be replaced, // then rearrangement impossible else { b = 1; break; } } } } // If neither of the configurations // worked then print "-1" if (b == 1) { System.out.print("-1" + " "); return; } // Otherwise, print the formed // rearrangement for(int i = 0; i < N; i++) { System.out.print(a[i] + " "); }}// Driver Codepublic static void main(String args[]){ // Given array int arr[] = { 1, -1, 2, 4, 0 }; // Size of array int N = arr.length; // Function Call rearrangeArray(arr, N);}}// This code is contributed by SURENDRA_GANGWAR |
Python3
# Python3 program for the above approach# Function to rearrange the array such# that sum of all elements of subarrays# from the 1st index is non-zerodef rearrangeArray(a, N): # Initialize sum of subarrays sum = 0 # Sum of all elements of array for i in range(N): sum += a[i] # If sum is 0, the required # array could never be formed if (sum == 0): print("-1") return # If sum is non zero, array # might be formed sum = 0 b = 0 # Sort array in ascending order a = sorted(a) for i in range(N): sum += a[i] # When current subarray sum # becomes 0 replace it with # the largest element if (sum == 0): if (a[i] != a[N - 1]): sum -= a[i] # Swap Operation a[i], a[N - 1] = a[N - 1], a[i] sum += a[i] # If largest element is same # as element to be replaced, # then rearrangement impossible else: b = 1 break # If b = 1, then rearrangement # is not possible. Hence check # with reverse configuration if (b == 1): b = 0 sum = 0 # Sort array in descending order a = sorted(a) a = a[::-1] # When current subarray sum # becomes 0 replace it with # the smallest element for i in range(N - 1, -1, -1): sum += a[i] if (sum == 0): if (a[i] != a[0]): sum -= a[i] # Swap Operation a[i], a[0] = a[0], a[i] sum += a[i] # If smallest element is same # as element to be replaced, # then rearrangement impossible else: b = 1 break # If neither of the configurations # worked then print"-1" if (b == 1): print("-1") return # Otherwise, print the formed # rearrangement for i in range(N): print(a[i], end = " ")# Driver Codeif __name__ == '__main__': # Given array arr = [ 1, -1, 2, 4, 0 ] # Size of array N = len(arr) # Function Call rearrangeArray(arr, N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Function to rearrange the array such// that sum of all elements of subarrays// from the 1st index is non-zerostatic void rearrangeArray(int [] a, int N){ // Initialize sum of subarrays int sum = 0; // Sum of all elements of array for(int i = 0; i < N; i++) { sum += a[i]; } // If sum is 0, the required // array could never be formed if (sum == 0) { Console.Write("-1"); return; } // If sum is non zero, array // might be formed sum = 0; int b = 0; // Sort array in ascending order Array.Sort(a); for(int i = 0; i < N; i++) { sum += a[i]; // When current subarray sum // becomes 0 replace it with // the largest element if (sum == 0) { if (a[i] != a[N - 1]) { sum -= a[i]; // Swap Operation int temp = a[i]; a[i] = a[N - 1]; a[N - 1] = temp; sum += a[i]; } // If largest element is same // as element to be replaced, // then rearrangement impossible else { b = 1; break; } } } // If b = 1, then rearrangement // is not possible. Hence check // with reverse configuration if (b == 1) { b = 0; sum = 0; // Sort array in descending order Array.Sort(a); // When current subarray sum // becomes 0 replace it with // the smallest element for(int i = N - 1; i >= 0; i--) { sum += a[i]; if (sum == 0) { if (a[i] != a[0]) { sum -= a[i]; // Swap Operation int temp = a[i]; a[i] = a[0]; a[0] = temp; sum += a[i]; } // If smallest element is same // as element to be replaced, // then rearrangement impossible else { b = 1; break; } } } } // If neither of the configurations // worked then print "-1" if (b == 1) { Console.Write("-1" + " "); return; } // Otherwise, print the formed // rearrangement for(int i = 0; i < N; i++) { Console.Write(a[i] + " "); }}// Driver Codepublic static void Main(){ // Given array int[] arr = { 1, -1, 2, 4, 0 }; // Size of array int N = arr.Length; // Function Call rearrangeArray(arr, N);}}// This code is contributed by chitranayal |
Javascript
<script>// javascript program for the// above approach// Function to rearrange the array such// that sum of all elements of subarrays// from the 1st index is non-zerofunction rearrangeArray(a, N){ // Initialize sum of subarrays let sum = 0; // Sum of all elements of array for(let i = 0; i < N; i++) { sum += a[i]; } // If sum is 0, the required // array could never be formed if (sum == 0) { document.write("-1"); return; } // If sum is non zero, array // might be formed sum = 0; let b = 0; // Sort array in ascending order a.sort(); for(let i = 0; i < N; i++) { sum += a[i]; // When current subarray sum // becomes 0 replace it with // the largest element if (sum == 0) { if (a[i] != a[N - 1]) { sum -= a[i]; // Swap Operation let temp = a[i]; a[i] = a[N - 1]; a[N - 1] = temp; sum += a[i]; } // If largest element is same // as element to be replaced, // then rearrangement impossible else { b = 1; break; } } } // If b = 1, then rearrangement // is not possible. Hence check // with reverse configuration if (b == 1) { b = 0; sum = 0; // Sort array in descending order a.sort(); // When current subarray sum // becomes 0 replace it with // the smallest element for(let i = N - 1; i >= 0; i--) { sum += a[i]; if (sum == 0) { if (a[i] != a[0]) { sum -= a[i]; // Swap Operation let temp = a[i]; a[i] = a[0]; a[0] = temp; sum += a[i]; } // If smallest element is same // as element to be replaced, // then rearrangement impossible else { b = 1; break; } } } } // If neither of the configurations // worked then print "-1" if (b == 1) { document.write("-1" + " "); return; } // Otherwise, print the formed // rearrangement for(let i = 0; i < N; i++) { document.write(a[i] + " "); }} // Driver Code // Given array let arr = [ 1, -1, 2, 4, 0 ]; // Size of array let N = arr.length; // Function Call rearrangeArray(arr, N); </script> |
Output:
-1 0 4 2 1
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
