Given an array arr[] consisting of N integers whose absolute values are distinct and an integer K, the task is to find such an arrangement of the given array by the following operations, such that it has positive prefix sum at exactly K places:
- Choose two integers i, j and swap the values of the element at indices i and j, where 0 ? i, j < N and i ? j.
- Choose an index i and change its sign i.e., change positive to negative and vice-versa where 0 ? i < N.
Examples:
Input: arr[] = {1, -2, 4, 5, -3}, K = 3
Output: {-1, 2, -4, 3, 5}
Explanation:
Prefix sums of the given array are {-1, 1, -3, 0, 5}.
Therefore, exactly 3 indices have positive prefix sum.Input: arr[] = {1, 4, 3, 2}, K = 2
Output: {1, -4, 2, 3}
Explanation:
Prefix sums of the given array are 1, -3, -1, 2}.
Therefore, exactly 2 indices have positive prefix sum.
Approach: The given problem can be solved by observing that one can get the sorted array using only the first type of operation. And one can change every element into positive elements using the 2nd type of operation. Follow the steps below to solve the problem:
- Make all the values of the array positive by using the 2nd operation i.e., flip the sign of all negative numbers to positive.
- Sort the array arr[] in ascending order and set K equal to (N – K).
- If the sum of K and the count of 0s in the given array arr[] is greater than N, then there can’t be any such possible arrangement. Hence print “-1”. Else perform the below operations.
- Traverse the array over the range [0, N – 1] and follow the below steps:
- Change the ith element into negative by the 2nd operation.
- Increment i by 2 and decrement K by 1.
- If K is equal to 0 then break.
- Check if K is still greater than 0, then traverse the array from last until K is greater than 0, and change every positive element into negative and decrement K by 1.
- After the above steps, print the array as the required arrangement.
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// according to the given conditionvoid rearrange(int* a, int n, int x){ // Using 2nd operation making // all values positive for (int i = 0; i < n; i++) a[i] = abs(a[i]); // Sort the array sort(a, a + n); // Assign K = N - K x = n - x; // Count number of zeros int z = count(a, a + n, 0); // If number of zeros if greater if (x > n - z) { cout << "-1\n"; return; } for (int i = 0; i < n && x > 0; i += 2) { // Using 2nd operation convert // it into one negative a[i] = -a[i]; x--; } for (int i = n - 1; i >= 0 && x > 0; i--) { // Using 2nd operation convert // it into one negative if (a[i] > 0) { a[i] = -a[i]; x--; } } // Print the array for (int i = 0; i < n; i++) { cout << a[i] << " "; }}// Driver Codeint main(){ int arr[] = { 0, -2, 4, 5, -3 }; int K = 3; int N = sizeof(arr) / sizeof(arr[0]); // Function Call rearrange(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*; class GFG{ static int count(int[] a){ int counter = 0; for(int i = 0; i < a.length; i++) { if (a[i] == 0) { counter++; } } return counter;}// Function to rearrange the array// according to the given conditionstatic void rearrange(int[] a, int n, int x){ // Using 2nd operation making // all values positive for(int i = 0; i < n; i++) a[i] = Math.abs(a[i]); // Sort the array Arrays.sort(a); // Assign K = N - K x = n - x; // Count number of zeros int z = count(a); // If number of zeros if greater if (x > n - z) { System.out.println("-1"); return; } for(int i = 0; i < n && x > 0; i += 2) { // Using 2nd operation convert // it into one negative a[i] = -a[i]; x--; } for(int i = n - 1; i >= 0 && x > 0; i--) { // Using 2nd operation convert // it into one negative if (a[i] > 0) { a[i] = -a[i]; x--; } } // Print the array for(int i = 0; i < n; i++) { System.out.print(a[i] + " "); }}// Driver Codepublic static void main (String[] args){ int arr[] = { 0, -2, 4, 5, -3 }; int K = 3; int N = arr.length; // Function Call rearrange(arr, N, K);}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to rearrange the array# according to the given conditiondef rearrange(a, n, x): # Using 2nd operation making # all values positive for i in range(n): a[i] = abs(a[i]) # Sort the array a = sorted(a) # Assign K = N - K x = n - x; # Count number of zeros z = a.count(0) # If number of zeros if greater if (x > n - z): print("-1") return for i in range(0, n, 2): if x <= 0: break # Using 2nd operation convert # it into one negative a[i] = -a[i] x -= 1 for i in range(n - 1, -1, -1): if x <= 0: break # Using 2nd operation convert # it into one negative if (a[i] > 0): a[i] = -a[i] x -= 1 # Print array for i in range(n): print(a[i], end = " ")# Driver Codeif __name__ == '__main__': arr = [0, -2, 4, 5, -3] K = 3 N = len(arr) # Function Call rearrange(arr, N, K) # This code is co tributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ static int count(int[] a){ int counter = 0; for(int i = 0; i < a.Length; i++) { if (a[i] == 0) { counter++; } } return counter;}// Function to rearrange the array// according to the given conditionstatic void rearrange(int[] a, int n, int x){ // Using 2nd operation making // all values positive for(int i = 0; i < n; i++) a[i] = Math.Abs(a[i]); // Sort the array Array.Sort(a); // Assign K = N - K x = n - x; // Count number of zeros int z = count(a); // If number of zeros if greater if (x > n - z) { Console.WriteLine("-1"); return; } for(int i = 0; i < n && x > 0; i += 2) { // Using 2nd operation convert // it into one negative a[i] = -a[i]; x--; } for(int i = n - 1; i >= 0 && x > 0; i--) { // Using 2nd operation convert // it into one negative if (a[i] > 0) { a[i] = -a[i]; x--; } } // Print the array for(int i = 0; i < n; i++) { Console.Write(a[i] + " "); }}// Driver Codepublic static void Main(String[] args){ int []arr = { 0, -2, 4, 5, -3 }; int K = 3; int N = arr.Length; // Function Call rearrange(arr, N, K);}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach function count(a) { let counter = 0; for(let i = 0; i < a.length; i++) { if (a[i] == 0) { counter++; } } return counter;} // Function to rearrange the array// according to the given conditionfunction rearrange(a, n, x){ // Using 2nd operation making // all values positive for(let i = 0; i < n; i++) a[i] = Math.abs(a[i]); // Sort the array a.sort(); // Assign K = N - K x = n - x; // Count number of zeros let z = count(a); // If number of zeros if greater if (x > n - z) { document.write("-1"); return; } for(let i = 0; i < n && x > 0; i += 2) { // Using 2nd operation convert // it into one negative a[i] = -a[i]; x--; } for(let i = n - 1; i >= 0 && x > 0; i--) { // Using 2nd operation convert // it into one negative if (a[i] > 0) { a[i] = -a[i]; x--; } } // Print the array for(let i = 0; i < n; i++) { document.write(a[i] + " "); }}// driver function let arr = [ 0, -2, 4, 5, -3 ]; let K = 3; let N = arr.length; // Function Call rearrange(arr, N, K); // This code is contributed by souravghosh0416.</script> |
Output:
0 2 -3 4 5
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!
