Minimum increments or decrements required to signs of prefix sum array elements alternating | C ++ 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 ; Case 1. neg - pos - neg ; Stores the current sign of the prefix sum of array ; Stores minimum number of operations for Case 1 ; Traverse the array ; Checking both conditions ; Update the current prefix1 to currentPrefixSum ; Case 2. pos - neg - pos ; Stores the prefix sum of array ; Stores minimum number of operations for Case 1 ; Checking both conditions ; Update the current prefix2 to currentPrefixSum ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minimumOperations ( int A [ ] , int N ) { int cur_prefix_1 = 0 ; int parity = -1 ; int minOperationsCase1 = 0 ; for ( int i = 0 ; i < N ; i ++ ) { cur_prefix_1 += A [ i ] ; if ( cur_prefix_1 == 0 parity * cur_prefix_1 < 0 ) { minOperationsCase1 += abs ( parity - cur_prefix_1 ) ; cur_prefix_1 = parity ; } parity *= -1 ; } int cur_prefix_2 = 0 ; parity = 1 ; int minOperationsCase2 = 0 ; for ( int i = 0 ; i < N ; i ++ ) { cur_prefix_2 += A [ i ] ; if ( cur_prefix_2 == 0 parity * cur_prefix_2 < 0 ) { minOperationsCase2 += abs ( parity - cur_prefix_2 ) ; cur_prefix_2 = parity ; } parity *= -1 ; } return min ( minOperationsCase1 , minOperationsCase2 ) ; } int main ( ) { int A [ ] = { 1 , -3 , 1 , 0 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << minimumOperations ( A , N ) ; return 0 ; }