Maximize pair decrements required to reduce all array elements except one to 0 | C ++ program to implement the above approach ; Function to count maximum number of steps to make ( N - 1 ) array elements to 0 ; Stores maximum count of steps to make ( N - 1 ) elements equal to 0 ; Stores array elements ; Traverse the array ; Insert arr [ i ] into PQ ; Extract top 2 elements from the array while ( N - 1 ) array elements become 0 ; Stores top element of PQ ; Pop the top element of PQ . ; Stores top element of PQ ; Pop the top element of PQ . ; Update X ; Update Y ; If X is not equal to 0 ; Insert X into PQ ; if Y is not equal to 0 ; Insert Y into PQ ; Update cntOp ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int cntMaxOperationToMakeN_1_0 ( int arr [ ] , int N ) { int cntOp = 0 ; priority_queue < int > PQ ; for ( int i = 0 ; i < N ; i ++ ) { PQ . push ( arr [ i ] ) ; } while ( PQ . size ( ) > 1 ) { int X = PQ . top ( ) ; PQ . pop ( ) ; int Y = PQ . top ( ) ; PQ . pop ( ) ; X -- ; Y -- ; if ( X != 0 ) { PQ . push ( X ) ; } if ( Y != 0 ) { PQ . push ( Y ) ; } cntOp += 1 ; } return cntOp ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << cntMaxOperationToMakeN_1_0 ( arr , N ) ; return 0 ; }