Make all array elements equal by replacing adjacent pairs by their sum | Java 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
import java . util . * ; class GFG { static int minSteps ( ArrayList < Integer > a , int n ) { int [ ] prefix_sum = new int [ n ] ; prefix_sum [ 0 ] = a . get ( 0 ) ; for ( int i = 1 ; i < n ; i ++ ) prefix_sum [ i ] += prefix_sum [ i - 1 ] + a . get ( i ) ; int mx = - 1 ; for ( int subgroupsum : prefix_sum ) { int sum = 0 ; int i = 0 ; int grp_count = 0 ; while ( i < n ) { sum += a . get ( 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 ; } public static void main ( String [ ] args ) { ArrayList < Integer > A = new ArrayList < Integer > ( ) ; A . add ( 1 ) ; A . add ( 2 ) ; A . add ( 3 ) ; A . add ( 2 ) ; A . add ( 1 ) ; A . add ( 3 ) ; int N = A . size ( ) ; System . out . print ( minSteps ( A , N ) ) ; } }