Minimize Operations to Make Arrays Equal

Approach to Solve

This problem can be solved using a greedy approach. It is a problem-solving strategy. It makes locally optimal choices at each step with the goal of finding an optimal solution. In a greedy approach, the algorithm evaluates the available options at each step. It chooses the best option based on some criteria without considering the future consequences or looking ahead to future steps.

The most important part of this problem is that we only need to decrement the values. This means if we have to make all of the elements in the array equal, then all the array values, in the end, will be equal to the array's minimum value. 

The greedy approach for this problem is calculating the minimum values in both arrays.

Take a pause and think about how to achieve this.  

• One way is to traverse both arrays and compute the difference between the current value and the minimum value of the array. 
   
• Let's say the differences are Diff1 and Diff2 for the arrays Arr1 and Arr2 respectively. 
   
• Let minValArr1 and minValArr2 be the minimum value in the arrays Arr1 and Arr2 respectively.  
   
• So, Diff1 is the number of operations of type 1 to make the current element of Arr1 equal to minValArr1.
   
• Similarly, Diff2 is the number of operations of type 2 to make the current element of Arr2 to minValArr2.
   
• If we only perform operations of type 1 and 2, then for the current index, we need a total of Diff1+Diff2 operations.
   
• But, is there a way to reduce the number of operations? Yes, by making use of the operations of type 3. 
   
• According to the operation of type 3, we can reduce the element at an index i in both arrays simultaneously. 
   
• So, we will decrement the elements Arr1[i] and Arr2[i] until either Arr1[i] becomes equal to minValArr1 or Arr2[i] becomes equal to minValArr2.
   
• This will take min(Diff1, Diff2) number of operations. 
   
• Now, one of Arr1[i] and Arr2[i] has achieved its target value. For the other one, we will need extra operations to make it achieve its minimum value. 
• The number of extra operations needed will be max(Diff1, Diff2)-min(Diff1, Diff2). 
   
• Therefore total number of operations required is min(Diff1, Diff2) + max(Diff1, Diff2)-min(Diff1, Diff2), which is equal to max(Diff1, Diff2).
   
• So, we will add the maximum of the minimum operation from both arrays to the answer. 
   

Let’s understand this with the help of an example.

Suppose we have two arrays,

Arr1=[1,5,3]

Arr2=[7,5,9]

We have to find the minimum element of the arrays,

minValArr1=1

minValArr2=5 

Now we will loop through the arrays,

At the index 0,

Diff1=Arr1[0]-minValArr1=1-1=0

Diff2=Arr2[0]-minValArr2=7-5=2

Now, to make the 0th element of both arrays equal to their minimum element then, we have to make two operations,

Decrement the Arr2[0] two times.

Now we have to find the minimum operations at index 0= max(2,0)=2
 

Now at index 1,

Diff1=Arr1[1]-minValArr1=5-1=4

Diff2=Arr2[1]-minValArr2=5-5=0

So the minimum operations at index 1=max(4,0)=4

Decrement Arr1[1] four times.

Now at index 2,

Diff1=Arr1[2]-minValArr1=3-1=2

Diff2=Arr2[2]-minValArr2=9-5=4

So the minimum operations at index 2=max(2,4)=4

Decrement Arr1[2] and Arr2[2] two times and then decrement Arr2[2] two times again.

So, the total number of operations is 2 + 4 + 4 = 10.

Let us understand the algorithm for this greedy approach.

Algorithm

Let us try to write an algorithm for the above-mentioned approach.

1. Find the minimum element of both arrays, i.e., minValArr1 = min_element(Arr1) and minValArr2 = min_element(Arr2). 
   In C++, we can use an STL(Standard Template Library) function *min_element() to find the minimum element.
    
2. Declare a count variable to store the minimum number of operations.
    
3. Then traverse through the arrays and calculate the difference between the current element and the minimum value. Add the maximum of these two differences into the count variable.
    
4. Return the count.

Code in C++

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


// Function to find the minimum number of operations to make both arrays equal
int minNumOps(vector<int> &arr1, vector<int> &arr2, int n)
{
   // Find the minimum value in arr1 and arr2
   int minValArr1 = *min_element(arr1.begin(), arr1.end());
   int minValArr2 = *min_element(arr2.begin(), arr2.end());


   // Variable to store the minimum count of operations.
   int count = 0;


   // Looping through the arrays 
   for (int i = 0; i < n; i++)
   {
       // Find the difference between the current value and the minimum value.
       int diff1 = arr1[i] - minValArr1;
       int diff2 = arr2[i] - minValArr2;


       // Add the maximum of the two differences into count.
       count += max(diff1, diff2);
   }


   // Return count of minimum operations to make arrays equal.
   return count;
}


int main()
{
   vector<int> arr1={2,8,6,4,5};
   vector<int> arr2={12,16,13,7,8};    
   int n=arr1.size();
   int minOperation = minNumOps(arr1, arr2, n);


   cout << "Minimum number of operations to make arrays equal: " << minOperation << endl;


   return 0;
}

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

Run Code

Output

Minimum number of operations to make arrays equal: 25

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

Run Code

Time Complexity

O(n), where 'n' is the size of 'Arr1' and 'Arr2'. Because we are looping through the arrays once, hence the time complexity is O(n). Also, the time complexity to minimum elements of both arrays is O(n). So, the final time complexity of this algorithm will be O(n).

Space Complexity

O(1) because we are not using any extra space.
Check out this problem - No of Spanning Trees in a Graph

Frequently Asked Questions

What is a greedy algorithm?

A greedy algorithm is an algorithmic paradigm. It follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

What is the advantage of using a greedy algorithm?

One of the advantages of using a greedy algorithm is that it is often easy to understand and implement. These algorithms are generally efficient. They can provide a good solution quickly. In some cases, greedy algorithms can also provide an optimal solution.

What are the problems that can be solved using the greedy approach?

The greedy approach is often simple to implement and can be quite efficient for certain types of problems. The problems that can be solved using the greedy approach are minimum spanning trees, Huffman coding, coin change, activity selection, etc.

What is the disadvantage of using a greedy algorithm?

One of the disadvantages of using a greedy algorithm is that it does not always guarantee an optimal solution. Sometimes the locally optimal choice can lead to a suboptimal solution globally. In some cases, greedy algorithms may not even find a feasible solution.

Conclusion

In this article, we have discussed how we can find the minimum operations to make arrays equal. We have discussed its approach, its algorithm, and C++ implementation along with time and space complexity analysis. 

You can check out other blogs on these kinds of problems.

• Check if the Anagram of X is Smaller than Y
   
• Job Scheduling Algorithm
   
• Maximize the Sum of Max and Min of K Subarrays
   

On the Coding Ninjas Platform, we have various such problems and blogs. Additionally, Coding Ninjas recently introduced the Coding Ninjas Studio Test Series, a mainly developed test series for acing interviews. Ace your coding interviews with Coding Ninjas Studio.

Happy Learning!!