Given an array, arr[ ] of size N, the task is to rearrange the given array such that the product of all the elements of its prefix sum array is not equal to 0. If it is not possible to rearrange the array that satisfies the given condition, then print -1.
Examples:
Input: arr[] = {1, -1, -2, 3}
Output: 3 1 -1 -2
Explanation:
Prefix sum after rearranging the given array to {3, 1, -1, -2} are {3, 4, 3, 1} and product all the elements of its prefix sum array = (3 * 4 * 3 * 1) = 36.
Therefore, the required array is {3, 1, -1, -2}Input: arr = {1, 1, -1, -1}
Output: -1
Approach: The idea is to sort the given array either in ascending order or descending order so that any element of its prefix sum not equal to 0. Follow the steps below to solve the problem:
- Calculate the sum of elements of the given array, say totalSum.
- If totalSum = 0 then print -1.
- If totalSum > 0 then print the given array in decreasing order so that any elements of its prefix sum not equal to 0.
- If totalSum < 0 then print the given array in ascending order so that any elements of its prefix sum not equal to 0.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to print array elementsvoid printArr(int arr[], int N){ for (int i = 0; i < N; i++) { cout << arr[i] << " "; }}// Function to rearrange array// that satisfies the given conditionvoid rearrangeArr(int arr[], int N){ // Stores sum of elements // of the given array int totalSum = 0; // Calculate totalSum for (int i = 0; i < N; i++) { totalSum += arr[i]; } // If the totalSum is equal to 0 if (totalSum == 0) { // No possible way to // rearrange array cout << "-1" << endl; } // If totalSum exceeds 0 else if (totalSum > 0) { // Rearrange the array // in descending order sort(arr, arr + N, greater<int>()); printArr(arr, N); } // Otherwise else { // Rearrange the array // in ascending order sort(arr, arr + N); printArr(arr, N); }}// Driver Codeint main(){ int arr[] = { 1, -1, -2, 3 }; int N = sizeof(arr) / sizeof(arr[0]); rearrangeArr(arr, N);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to print array elementsstatic void printArr(int arr[], int N){ for(int i = 0; i < N; i++) { System.out.print(arr[i] + " "); }}// Function to rearrange array// that satisfies the given conditionstatic void rearrangeArr(int arr[], int N){ // Stores sum of elements // of the given array int totalSum = 0; // Calculate totalSum for(int i = 0; i < N; i++) { totalSum += arr[i]; } // If the totalSum is equal to 0 if (totalSum == 0) { // No possible way to // rearrange array System.out.print("-1" + "\n"); } // If totalSum exceeds 0 else if (totalSum > 0) { // Rearrange the array // in descending order Arrays.sort(arr); arr = reverse(arr); printArr(arr, N); } // Otherwise else { // Rearrange the array // in ascending order Arrays.sort(arr); printArr(arr, N); }}static int[] reverse(int a[]){ int i, n = a.length, t; for(i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, -1, -2, 3 }; int N = arr.length; rearrangeArr(arr, N);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement# the above approach# Function to rearrange array# that satisfies the given conditiondef rearrangeArr(arr, N): # Stores sum of elements # of the given array totalSum = 0 # Calculate totalSum for i in range(N): totalSum += arr[i] # If the totalSum is equal to 0 if (totalSum == 0): # No possible way to # rearrange array print(-1) # If totalSum exceeds 0 elif (totalSum > 0): # Rearrange the array # in descending order arr.sort(reverse = True) print(*arr, sep = ' ') # Otherwise else: # Rearrange the array # in ascending order arr.sort() print(*arr, sep = ' ')# Driver Codearr = [ 1, -1, -2, 3 ]N = len(arr)rearrangeArr(arr, N);# This code is contributed by avanitrachhadiya2155 |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to print array elementsstatic void printArr(int []arr, int N){ for(int i = 0; i < N; i++) { Console.Write(arr[i] + " "); }}// Function to rearrange array// that satisfies the given conditionstatic void rearrangeArr(int []arr, int N){ // Stores sum of elements // of the given array int totalSum = 0; // Calculate totalSum for(int i = 0; i < N; i++) { totalSum += arr[i]; } // If the totalSum is equal to 0 if (totalSum == 0) { // No possible way to // rearrange array Console.Write("-1" + "\n"); } // If totalSum exceeds 0 else if (totalSum > 0) { // Rearrange the array // in descending order Array.Sort(arr); arr = reverse(arr); printArr(arr, N); } // Otherwise else { // Rearrange the array // in ascending order Array.Sort(arr); printArr(arr, N); }}static int[] reverse(int []a){ int i, n = a.Length, t; for(i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;}// Driver Codepublic static void Main(String[] args){ int []arr = { 1, -1, -2, 3 }; int N = arr.Length; rearrangeArr(arr, N);}}// This code is contributed by Princi Singh |
Javascript
<script>// javascript program to implement// the above approach // Function to print array elementsfunction printArr(arr, N){ for(var i = 0; i < N; i++) { document.write(arr[i] + " "); }} // Function to rearrange array// that satisfies the given condition function rearrangeArr(arr, N){ // Stores sum of elements // of the given array var totalSum = 0; // Calculate totalSum for(var i = 0; i < N; i++) { totalSum += arr[i]; } // If the totalSum is equal to 0 if (totalSum == 0) { // No possible way to // rearrange array document.write("-1" + "<br>"); } // If totalSum exceeds 0 else if (totalSum > 0) { // Rearrange the array // in descending order arr.sort(compare); arr = reverse(arr); printArr(arr, N); } // Otherwise else { // Rearrange the array // in ascending order arr.sort(compare); printArr(arr, N); }}function compare(a, b) { if (a < b) { return -1; } else if (a > b) { return 1; } else { return 0; }} function reverse(a){ var i, n = a.length, t; for(i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;} // Driver Code var arr = [ 1, -1, -2, 3 ] ; var N = arr.length; rearrangeArr(arr, N); </script> |
Output:
3 1 -1 -2
Time Complexity: O(N logN)
Space Complexity: 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!
