Data Modelling & AI Data Structure & Algorithm

Make all array elements equal by replacing adjacent pairs by their sum

23 June 2025

0

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 equal
int 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 Code
int 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 approach
import 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 equal
static 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 Code
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();
 
  // 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 equal
def 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 Code
if __name__ == '__main__':
   
    A = [1, 2, 3, 2, 1, 3]
    N = len(A)
     
    # Function Call
    print(minSteps(A, N))

C#

// C# program for the above approach
using 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 equal
static 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 Code
public 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 equal
function 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 Code
var A = [1, 2, 3, 2, 1, 3];
var N = A.length;
 
// Function Call
document.write( minSteps(A, N));
 
 
</script>

Output:

Time Complexity: O(N²), as we are using nested loops to traverse N² 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 neveropen!

Make all array elements equal by replacing adjacent pairs by their sum

C++

Java

Python3

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

Google’s 15 year old Pixel concept. [Video]

The one feature Samsung Wallet still can’t get right — and probably never will

I regret trading in my Pixel 8 so early

Forget Bluetooth — this Android feature makes sharing files to a Mac ridiculously easy

EDITOR PICKS

Google’s 15 year old Pixel concept. [Video]

The one feature Samsung Wallet still can’t get right — and probably never will

I regret trading in my Pixel 8 so early

POPULAR POSTS

Google’s 15 year old Pixel concept. [Video]

The one feature Samsung Wallet still can’t get right — and probably never will

I regret trading in my Pixel 8 so early

POPULAR CATEGORY

ABOUT US

FOLLOW US