Make all array elements equal by replacing adjacent pairs by their sum | Function to count the minimum number of pairs of adjacent elements required to be replaced by their sum to make all arrat 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
def minSteps ( a , n ) : NEW_LINE INDENT prefix_sum = a [ : ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT prefix_sum [ i ] += prefix_sum [ i - 1 ] NEW_LINE DEDENT mx = - 1 NEW_LINE for subgroupsum in prefix_sum : NEW_LINE INDENT sum = 0 NEW_LINE i = 0 NEW_LINE grp_count = 0 NEW_LINE while i < n : NEW_LINE INDENT sum += a [ i ] NEW_LINE if sum == subgroupsum : NEW_LINE INDENT grp_count += 1 NEW_LINE sum = 0 NEW_LINE DEDENT elif sum > subgroupsum : NEW_LINE INDENT grp_count = - 1 NEW_LINE break NEW_LINE DEDENT i += 1 NEW_LINE DEDENT if grp_count > mx : NEW_LINE INDENT mx = grp_count NEW_LINE DEDENT DEDENT return n - mx NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 1 , 2 , 3 , 2 , 1 , 3 ] NEW_LINE N = len ( A ) NEW_LINE print ( minSteps ( A , N ) ) NEW_LINE DEDENT