Minimum increments or decrements required to signs of prefix sum array elements alternating
Given an array arr[] of N integers, the task is to find the minimum number of increments/decrements of array elements by 1 to make the sign of prefix sum of array alternating.
Examples:
Input: arr[] = {1, -3, 1, 0}
Output: 4
Explanation:
Following are the operations performed on the given array elements:
- Incrementing the array element arr[1](= -3) by 1 modifies the array to {1, -2, 1, 0}.
- Incrementing the array element arr[2](= 1) by 1 modifies the array to {1, -2, 2, 0}.
- Decrementing the array element arr[3](= 0) by 1 modifies the array to {1, -2, 2, -1}.
- Decrementing the array element arr[3](= -1) by 1 modifies the array to {1, -2, 2, -2}.
After the above operations, the prefix sum of the modified array is {1, -1, 1, -1}, which is in alternate order of sign. Therefore, the minimum number of operations required is 4.
Input: arr[] = {3, -6, 4, -5, 7}
Output: 0
Approach: The given problem can be solved by modifying the array element using the given operations in both the order i.e., positive, negative, positive, … or negative, positive, negative, …, and print the minimum of the two operations required. Follow the steps below to solve the given problem:
- For Case 1: modifying the array element in the order of negative, positive, negative:
- Initialize variables current_prefix_1 as 0 that stores the prefix sum of the array.
- Initialize variables minOperationCase1 as 0 that stores the resultant minimum number of operations required.
- Traverse the given array and perform the following steps:
- Increment the current_prefix_1 by arr[i].
- If the value of current_prefix_1 or the parity is -ve, then increment the minimum number of operations by the abs(parity – current_prefix_1).
- Multiply the parity by (-1).
- Similarly, as discussed in Case 1, find the minimum number of operations required for the order of prefix sum as positive, negative, positive, … and store it in a variable minOperationCase2.
- After completing the above steps, print the minimum of minOperationCase1 and minOperationCase2 as the resultant operations required.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number // of increments/decrements of array // elements by 1 to make signs of // prefix sum array elements alternating int minimumOperations( int A[], int N) { // Case 1. neg - pos - neg int cur_prefix_1 = 0; // Stores the current sign of // the prefix sum of array int parity = -1; // Stores minimum number of operations // for Case 1 int minOperationsCase1 = 0; // Traverse the array for ( int i = 0; i < N; i++) { cur_prefix_1 += A[i]; // Checking both conditions if (cur_prefix_1 == 0 || parity * cur_prefix_1 < 0) { minOperationsCase1 += abs (parity - cur_prefix_1); // Update the current prefix1 to // currentPrefixSum cur_prefix_1 = parity; } parity *= -1; } // Case 2. pos - neg - pos int cur_prefix_2 = 0; // Stores the prefix sum of array parity = 1; // Stores minimum number of operations // for Case 1 int minOperationsCase2 = 0; for ( int i = 0; i < N; i++) { cur_prefix_2 += A[i]; // Checking both conditions if (cur_prefix_2 == 0 || parity * cur_prefix_2 < 0) { minOperationsCase2 += abs (parity - cur_prefix_2); // Update the current prefix2 to // currentPrefixSum cur_prefix_2 = parity; } parity *= -1; } return min(minOperationsCase1, minOperationsCase2); } // Driver Code int main() { int A[] = { 1, -3, 1, 0 }; int N = sizeof (A) / sizeof (A[0]); cout << minimumOperations(A, N); return 0; } |
Java
// Java code for above approach import java.util.*; class GFG{ // Function to find the minimum number // of increments/decrements of array // elements by 1 to make signs of // prefix sum array elements alternating static int minimumOperations( int A[], int N) { // Case 1. neg - pos - neg int cur_prefix_1 = 0 ; // Stores the current sign of // the prefix sum of array int parity = - 1 ; // Stores minimum number of operations // for Case 1 int minOperationsCase1 = 0 ; // Traverse the array for ( int i = 0 ; i < N; i++) { cur_prefix_1 += A[i]; // Checking both conditions if (cur_prefix_1 == 0 || parity * cur_prefix_1 < 0 ) { minOperationsCase1 += Math.abs(parity - cur_prefix_1); // Update the current prefix1 to // currentPrefixSum cur_prefix_1 = parity; } parity *= - 1 ; } // Case 2. pos - neg - pos int cur_prefix_2 = 0 ; // Stores the prefix sum of array parity = 1 ; // Stores minimum number of operations // for Case 1 int minOperationsCase2 = 0 ; for ( int i = 0 ; i < N; i++) { cur_prefix_2 += A[i]; // Checking both conditions if (cur_prefix_2 == 0 || parity * cur_prefix_2 < 0 ) { minOperationsCase2 += Math.abs(parity - cur_prefix_2); // Update the current prefix2 to // currentPrefixSum cur_prefix_2 = parity; } parity *= - 1 ; } return Math.min(minOperationsCase1, minOperationsCase2); } // Driver Code public static void main(String[] args) { int A[] = { 1 , - 3 , 1 , 0 }; int N = A.length; System.out.print(minimumOperations(A, N)); } } // This code is contributed by avijitmondal1998. |
Python3
# Python program for the above approach # Function to find the minimum number # of increments/decrements of array # elements by 1 to make signs of # prefix sum array elements alternating def minimumOperations(A, N) : # Case 1. neg - pos - neg cur_prefix_1 = 0 # Stores the current sign of # the prefix sum of array parity = - 1 # Stores minimum number of operations # for Case 1 minOperationsCase1 = 0 # Traverse the array for i in range (N) : cur_prefix_1 + = A[i] # Checking both conditions if (cur_prefix_1 = = 0 or parity * cur_prefix_1 < 0 ) : minOperationsCase1 + = abs (parity - cur_prefix_1) # Update the current prefix1 to # currentPrefixSum cur_prefix_1 = parity parity * = - 1 # Case 2. pos - neg - pos cur_prefix_2 = 0 # Stores the prefix sum of array parity = 1 # Stores minimum number of operations # for Case 1 minOperationsCase2 = 0 for i in range (N) : cur_prefix_2 + = A[i] # Checking both conditions if (cur_prefix_2 = = 0 or parity * cur_prefix_2 < 0 ) : minOperationsCase2 + = abs (parity - cur_prefix_2) # Update the current prefix2 to # currentPrefixSum cur_prefix_2 = parity parity * = - 1 return min (minOperationsCase1, minOperationsCase2) # Driver Code A = [ 1 , - 3 , 1 , 0 ] N = len (A) print (minimumOperations(A, N)) # This code is contributed by splevel62. |
C#
// C# code for above approach using System; public class GFG { // Function to find the minimum number // of increments/decrements of array // elements by 1 to make signs of // prefix sum array elements alternating static int minimumOperations( int []A, int N) { // Case 1. neg - pos - neg int cur_prefix_1 = 0; // Stores the current sign of // the prefix sum of array int parity = -1; // Stores minimum number of operations // for Case 1 int minOperationsCase1 = 0; // Traverse the array for ( int i = 0; i < N; i++) { cur_prefix_1 += A[i]; // Checking both conditions if (cur_prefix_1 == 0 || parity * cur_prefix_1 < 0) { minOperationsCase1 += Math.Abs(parity - cur_prefix_1); // Update the current prefix1 to // currentPrefixSum cur_prefix_1 = parity; } parity *= -1; } // Case 2. pos - neg - pos int cur_prefix_2 = 0; // Stores the prefix sum of array parity = 1; // Stores minimum number of operations // for Case 1 int minOperationsCase2 = 0; for ( int i = 0; i < N; i++) { cur_prefix_2 += A[i]; // Checking both conditions if (cur_prefix_2 == 0 || parity * cur_prefix_2 < 0) { minOperationsCase2 += Math.Abs(parity - cur_prefix_2); // Update the current prefix2 to // currentPrefixSum cur_prefix_2 = parity; } parity *= -1; } return Math.Min(minOperationsCase1, minOperationsCase2); } // Driver Code public static void Main(String[] args) { int []A = { 1, -3, 1, 0 }; int N = A.Length; Console.Write(minimumOperations(A, N)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program for the above approach // Function to find the minimum number // of increments/decrements of array // elements by 1 to make signs of // prefix sum array elements alternating function minimumOperations(A, N) { // Case 1. neg - pos - neg let cur_prefix_1 = 0; // Stores the current sign of // the prefix sum of array let parity = -1; // Stores minimum number of operations // for Case 1 let minOperationsCase1 = 0; // Traverse the array for (let i = 0; i < N; i++) { cur_prefix_1 += A[i]; // Checking both conditions if (cur_prefix_1 == 0 || parity * cur_prefix_1 < 0) { minOperationsCase1 += Math.abs(parity - cur_prefix_1); // Update the current prefix1 to // currentPrefixSum cur_prefix_1 = parity; } parity *= -1; } // Case 2. pos - neg - pos let cur_prefix_2 = 0; // Stores the prefix sum of array parity = 1; // Stores minimum number of operations // for Case 1 let minOperationsCase2 = 0; for (let i = 0; i < N; i++) { cur_prefix_2 += A[i]; // Checking both conditions if (cur_prefix_2 == 0 || parity * cur_prefix_2 < 0) { minOperationsCase2 += Math.abs(parity - cur_prefix_2); // Update the current prefix2 to // currentPrefixSum cur_prefix_2 = parity; } parity *= -1; } return Math.min(minOperationsCase1, minOperationsCase2); } // Driver Code let A = [1, -3, 1, 0]; let N = A.length; document.write(minimumOperations(A, N)); // This code is contributed by _saurabh_jaiswal. </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)