text: Make all array elements equal by replacing adjacent pairs by their sum | C ++ program for the above approach ; Function to count the minimum number of pairs of adjacent elements required to be replaced by their sum to make all array elements equal ; Stores the prefix sum of the array ; Calculate the prefix sum array ; Stores the maximum number of subarrays into which the array can be split ; Iterate over all possible sums ; Traverse the array ; If the sum is equal to the current prefix sum ; Increment count of groups by 1 ; Otherwise discard this subgroup sum ; Update the maximum this of subarrays ; Return the minimum number of operations ; Driver Code ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int minSteps ( vector < int > a , int n ) { vector < int > prefix_sum ( n ) ; prefix_sum [ 0 ] = a [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) prefix_sum [ i ] += prefix_sum [ i - 1 ] + a [ i ] ; int mx = -1 ; for ( int subgroupsum : prefix_sum ) { int sum = 0 ; int i = 0 ; int grp_count = 0 ; while ( i < n ) { sum += a [ i ] ; if ( sum == subgroupsum ) { grp_count += 1 ; sum = 0 ; } else if ( sum > subgroupsum ) { grp_count = -1 ; break ; } i += 1 ; } if ( grp_count > mx ) mx = grp_count ; } return n - mx ; } int main ( ) { vector < int > A = { 1 , 2 , 3 , 2 , 1 , 3 } ; int N = A . size ( ) ; cout << minSteps ( A , N ) ; return 0 ; }