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

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

The Pixel 10 Pro Fold sets itself apart with this one thing you don’t see

T-Mobile’s Pixel 10 Pro Fold deal knocks $1,000 off and includes a free pair of Pixel Buds 2a

Samsung Galaxy XR leak provides us with our best look yet at what to expect

Samsung’s upcoming tri-fold phone could flex its power with a massive battery setup

EDITOR PICKS

The Pixel 10 Pro Fold sets itself apart with this one thing you don’t see

T-Mobile’s Pixel 10 Pro Fold deal knocks $1,000 off and includes a free pair of Pixel Buds 2a

Samsung Galaxy XR leak provides us with our best look yet at what to expect

POPULAR POSTS

The Pixel 10 Pro Fold sets itself apart with this one thing you don’t see

T-Mobile’s Pixel 10 Pro Fold deal knocks $1,000 off and includes a free pair of Pixel Buds 2a

Samsung Galaxy XR leak provides us with our best look yet at what to expect

POPULAR CATEGORY

ABOUT US

FOLLOW US