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

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

You can also try this code with Online C++ Compiler

Run Code

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 i^th 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 - 

• Sum Of Two Arrays.
• Merge K Sorted Arrays.
• Intersection Of Two Arrays.

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.