Make all array elements equal by replacing adjacent pairs by their sum
Given an array arr[] consisting of N integers, the task is to replace a minimum number of pairs of adjacent elements by their sum to make all array elements equal. Print the minimum number of such operations required.
Examples:
Input: arr[] = {1, 2, 3}
Output: 1
Explanation: Replace arr[0] and arr[1] by their sum. Therefore, the array modifies to {3, 3}.
After completing the above operations, all the array elements become equal.
Therefore, the number of operations required is 1.Input: arr[] = {4, 4, 4}
Output: 0
Approach: The given problem can be solved using Prefix Sum Array technique. Follow the steps below to solve the given problem:
- Initialize a variable, say count, to store the maximum count of subarrays that can be obtained for any given sum value.
- Initialize an auxiliary array prefix[], of size N, and store the prefix sum of the given array arr[] in it.
- Traverse the array prefix[] and for each element prefix[i], perform the following steps:
- Check whether the given array arr[] can be divided into subarrays with sum prefix[i] or not. If found to be true, then store the count of such subarrays in a variable, say ans.
- Update the value of count as the maximum of count and ans.
- After completing the above steps, print the value of (N – count) as the minimum number of operations required.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the minimum number// of pairs of adjacent elements required// to be replaced by their sum to make all// array elements equalint minSteps(vector<int> a, int n){ // Stores the prefix sum of the array vector<int> prefix_sum(n); prefix_sum[0] = a[0]; // Calculate the prefix sum array for (int i = 1; i < n; i++) prefix_sum[i] += prefix_sum[i - 1] + a[i]; // Stores the maximum number of subarrays // into which the array can be split int mx = -1; // Iterate over all possible sums for (int subgroupsum :prefix_sum) { int sum = 0; int i = 0; int grp_count = 0; // Traverse the array while (i < n) { sum += a[i]; // If the sum is equal to // the current prefix sum if (sum == subgroupsum) { // Increment count // of groups by 1 grp_count += 1; sum = 0; } // Otherwise discard // this subgroup sum else if(sum > subgroupsum) { grp_count = -1; break; } i += 1; } // Update the maximum // this of subarrays if (grp_count > mx) mx = grp_count; } // Return the minimum // number of operations return n - mx;}// Driver Codeint main(){ vector<int> A = {1, 2, 3, 2, 1, 3}; int N = A.size(); // Function Call cout << minSteps(A, N); return 0;}// This code is contributed by mohit kumar 29. |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count the minimum number// of pairs of adjacent elements required// to be replaced by their sum to make all// array elements equalstatic int minSteps(ArrayList<Integer> a, int n){ // Stores the prefix sum of the array int []prefix_sum = new int[n]; prefix_sum[0] = a.get(0); // Calculate the prefix sum array for(int i = 1; i < n; i++) prefix_sum[i] += prefix_sum[i - 1] + a.get(i); // Stores the maximum number of subarrays // into which the array can be split int mx = -1; // Iterate over all possible sums for(int subgroupsum : prefix_sum) { int sum = 0; int i = 0; int grp_count = 0; // Traverse the array while (i < n) { sum += a.get(i); // If the sum is equal to // the current prefix sum if (sum == subgroupsum) { // Increment count // of groups by 1 grp_count += 1; sum = 0; } // Otherwise discard // this subgroup sum else if(sum > subgroupsum) { grp_count = -1; break; } i += 1; } // Update the maximum // this of subarrays if (grp_count > mx) mx = grp_count; } // Return the minimum // number of operations return n - mx;}// Driver Codepublic 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(); // Function Call System.out.print(minSteps(A, N));}}// This code is contributed by sanjoy_62 |
Python3
# Python3 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 equaldef minSteps(a, n): # Stores the prefix sum of the array prefix_sum = a[:] # Calculate the prefix sum array for i in range(1, n): prefix_sum[i] += prefix_sum[i-1] # Stores the maximum number of subarrays # into which the array can be split mx = -1 # Iterate over all possible sums for subgroupsum in prefix_sum: sum = 0 i = 0 grp_count = 0 # Traverse the array while i < n: sum += a[i] # If the sum is equal to # the current prefix sum if sum == subgroupsum: # Increment count # of groups by 1 grp_count += 1 sum = 0 # Otherwise discard # this subgroup sum elif sum > subgroupsum: grp_count = -1 break i += 1 # Update the maximum # this of subarrays if grp_count > mx: mx = grp_count # Return the minimum # number of operations return n - mx# Driver Codeif __name__ == '__main__': A = [1, 2, 3, 2, 1, 3] N = len(A) # Function Call print(minSteps(A, N)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to count the minimum number// of pairs of adjacent elements required// to be replaced by their sum to make all// array elements equalstatic int minSteps(List<int> a, int n){ // Stores the prefix sum of the array int []prefix_sum = new int[n]; prefix_sum[0] = a[0]; // Calculate the prefix sum array for (int i = 1; i < n; i++) prefix_sum[i] += prefix_sum[i - 1] + a[i]; // Stores the maximum number of subarrays // into which the array can be split int mx = -1; // Iterate over all possible sums foreach (int subgroupsum in prefix_sum) { int sum = 0; int i = 0; int grp_count = 0; // Traverse the array while (i < n) { sum += a[i]; // If the sum is equal to // the current prefix sum if (sum == subgroupsum) { // Increment count // of groups by 1 grp_count += 1; sum = 0; } // Otherwise discard // this subgroup sum else if(sum > subgroupsum) { grp_count = -1; break; } i += 1; } // Update the maximum // this of subarrays if (grp_count > mx) mx = grp_count; } // Return the minimum // number of operations return n - mx;}// Driver Codepublic static void Main(){ List<int> A = new List<int>(){1, 2, 3, 2, 1, 3}; int N = A.Count; // Function Call Console.Write(minSteps(A, N));}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script>// Javascript 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 equalfunction minSteps(a, n){ // Stores the prefix sum of the array var prefix_sum = Array(n).fill(0); prefix_sum[0] = a[0]; // Calculate the prefix sum array for (var i = 1; i < n; i++) prefix_sum[i] += prefix_sum[i - 1] + a[i]; // Stores the maximum number of subarrays // into which the array can be split var mx = -1; // Iterate over all possible sums for (var subgroupsum =0; subgroupsum<prefix_sum.length; subgroupsum++) { var sum = 0; var i = 0; var grp_count = 0; // Traverse the array while (i < n) { sum += a[i]; // If the sum is equal to // the current prefix sum if (sum == prefix_sum[subgroupsum]) { // Increment count // of groups by 1 grp_count += 1; sum = 0; } // Otherwise discard // this subgroup sum else if(sum > prefix_sum[subgroupsum]) { grp_count = -1; break; } i += 1; } // Update the maximum // this of subarrays if (grp_count > mx) mx = grp_count; } // Return the minimum // number of operations return n - mx;}// Driver Codevar A = [1, 2, 3, 2, 1, 3];var N = A.length;// Function Calldocument.write( minSteps(A, N));</script> |
Output:
2
Time Complexity: O(N2), as we are using nested loops to traverse N2 times.
Auxiliary Space: O(N), as we are using extra space for prefix_sum.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
