Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction-  
2.
Solution Approach 
3.
Algorithm -
4.
C++ code:
5.
Algorithm Complexity: 
6.
FAQs
7.
Key takeaways-
Last Updated: Mar 27, 2024

Make all Array Elements Equal by Replacing Consecutive occurrences of a Number Repeatedly

Author Riya
1 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction-  

This blog will discuss the problem to make all array elements equal by replacing consecutive occurrences of a number repeatedly

In this problem, we will be given an array of integers of size ‘N’ and we have to find the minimum number of steps required to make all the array elements equal. In one step, we have to perform the following two substeps:

  1. First, select a number between 1 and N
  2. Then choose a number from the array and replace all its consecutive equal elements with the number selected in substep ‘a’.


Let's understand the problem with an example:

Suppose given N and array are:

N = 5

arr = {3, 4, 1, 4, 3}

In step 1:

  1. Select a number ‘4’
  2. Then choose 1 in the ‘arr’ ({3, 4, 1, 4, 3})  and replace all consecutive equal elements with 4

 

After this step, the array will be changed to:  arr = {3, 4, 4, 4, 3}

In step 2:

  1. Select a number ‘3’ 
  2. Then choose 4 in the array ({3, 4, 4, 4, 3})  and replace all consecutive equal elements with 3

 

After this step, the array will be changed to:  arr = {3, 3, 3, 3, 3}

In this example, the output should be ‘2’ as a minimum of two steps are required to  make all array elements equal by replacing consecutive occurrences of a number repeatedly

Now that we understand the problem, let's discuss the approach to solve it in the next section.

Also Read, Byte Array to String

Solution Approach 

This section will discuss the approach to find the minimum steps required to make all array elements equal by replacing consecutive occurrences of a number repeatedly. This problem can be thought of as we have to remove all the elements of the given array by removing one set of consecutive equal elements at one step. This can be solved by using the concept of dynamic programming. Make a ‘dp’ table in which dp[i][j] stores the minimum steps required to remove the elements from ‘arr[i]’ to ‘arr[j]’. First fill the table with the base case that ‘dp[i][i] = 1’ as removing one element ‘arr[i]’ will require one step. Next for each i<j, dp[i][j] will be equal to dp[i][j-1] +1 if there will be no equal elements between ‘i’ and ‘j’. And if we find an element having a value equal to ‘arr[j]’, then we can update the value of dp[i][j] as we can delete the equal consecutive elements in one step only.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm -

Step 1. Create a function "minRequiredSteps()" to find the minimum steps required to make all array elements equal by replacing consecutive occurrences of a number repeatedly, which will accept two inputs - the given vector of integers and its size ‘N’.

Step 2. Inside the function "minRequiredSteps()",  first remove all the consecutive elements of the vector and resize it. 

Step 3. Now, declare a 2-dimensional array ‘dp’ to store the number of steps required to remove elements from index 'left' to 'right'  for each pair of indices ‘'left' and 'right', by removing consecutive equal elements repeatedly

Step 4. Now run a for loop for iterating from 0 to N as the right of the subarray we are considering. For each value of ‘right’ first, write the base case as ‘dp[right][right] = 1’ because removing the subarray of size 1 will require 1 step. 

Step 5.  Next using vectors ‘B’ and ‘C’, store the vector elements which are equal to the element at position ‘right’ in the vector ‘A’. Now for each value of ‘right’, run a ‘for loop’ for iterating through all possible values of ‘left’ of the subarray to be considered. For each value of ‘left’ and ‘right’, find the minimum number of steps required to remove the elements of that subarray and store it in the ‘dp’ array.

Step 6. Finally, the value stored in the dp[0][N-1] corresponds to the number of steps required to remove elements from index  '0’ to 'N-1' by removing consecutive equal elements repeatedly. So, the minimum number of steps required to make all array elements from ‘0’ to ‘N-1’ equal by replacing consecutive occurrences of a number repeatedly is dp[0][N-1].

C++ code:

// C++ program for finding the minimum steps required to make all array elements equal by replacing consecutive occurrences of a number repeatedly
#include <bits/stdc++.h>
using namespace std;


// Function for finding the minimum steps required to make all array elements equal by replacing consecutive occurrences of a number repeatedly
int minRequiredSteps(vector<int> A, int N)
{
	int x = 0;

    // Removing the consecutive elements
	for (int i = 1; i < N; ++i)
	{
		if (A[i] != A[x]) 
		{
			x = x+1;
			A[x] = A[i];
		}
	}
    	
    // Final size of the array after removing all the consecutive elements
	N = x + 1;
	A.resize(N);

    /*
         Declaring the dp array to store the number of steps required to remove
         elements from index 'left' to 'right' for each pair of 'left' and
        'right', by  removing consecutive equal elements repeatedly 
    */
    int dp[N][N];
    
    // Declaring vectors to keep track of elements with same value
    vector<int> B(N + 1, -1);
    vector<int> C(N, -1);


	for (int right = 0; right < N; right++)
	{
		dp[right][right] = 1;


		C[right] = B[A[right]];
		B[A[right]] = right;


		for (int left = right - 1; left >= 0; left--) 
		{
			int min_steps = dp[left][right - 1] + 1;

            // Update min_steps using all the indices having element equal to the element at index right
			for (int i = C[right]; i > left; i = C[i])
			{
				min_steps = min(min_steps, dp[left][i - 1] + dp[i][right]);
			}

            // If the elements at indices left and right are equal 
			if (A[left] == A[right]) 
			{
			    min_steps = min(min_steps, dp[left + 1][right]);
			}
            dp[left][right] = min_steps;
		}
	}

     return dp[0][N - 1] - 1;
}


// Main Function
int main()
{

	// Given array
	vector<int> A = { 3, 4, 1, 4, 3 };

	// Size of the array
	int N = A.size();
	
    /*
      	Call the function for finding the minimum steps required to make all array
      	elements equal by replacing consecutive occurrences of a number repeatedly
    */
    cout<<"The minimum steps required to make all array elements equal by replacing consecutive occurrences of a number repeatedly are: "<<minRequiredSteps(A, N);


	return 0;
}

 

Output:
The minimum steps required to make all array elements equal by replacing consecutive occurrences of a number repeatedly are: 2

Algorithm Complexity: 

Time Complexity: O(N ^ 3)

In the function "minRequiredSteps()" to find the minimum steps required to make all array elements equal by replacing consecutive occurrences of a number repeatedly, three nested loops are run, each having a maximum iteration of N. So, the overall time complexity is O(N ^ 3), where 'N' is the length of the given array.

Space Complexity: O(N ^ 2) 

In the function "minRequiredSteps()" to find the minimum steps required to make all array elements equal by replacing consecutive occurrences of a number repeatedly, we have created a 2-dimensional array of size N^2. So, the space complexity is O(N ^ 2), where 'N' is the length of the given array. 

Check out this problem - Longest Subarray With Sum K 

FAQs

  1. In the above dynamic approach solution, what does the state dp[i][j] represent?
    In the above dynamic programming solution, dp[i][j] represents the minimum number of steps required to remove all the elements between indices ‘i’ and ‘j’ (both inclusive) from the array. 
     
  2. In the above dynamic approach solution, why we have used the base case “dp[i][i] = 1”?
    In the solution, dp[i][i] represents the minimum number of steps required to remove the ith element from the array and there will be one step required to remove any one element of the array which is our base case.

Key takeaways-

This article discussed the problem  "Make all array elements equal by replacing consecutive occurrences of a number repeatedly," the solution approach to this problem,  its C++ implementation, and its time and space complexity.

If you want to solve similar problems on data structures and algorithms for practice, you can visit Coding Ninjas Studio.

 Check out the following problems - 


If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

 

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Super Ugly Numbers
Next article
Smallest Subarray With All Occurrences of the Most Frequent Element
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass