Minimum operations to make all elements equal in array in C++

Hello learners, today in this tutorial we will learn how to count minimum number operations to make all elements equal in an array in C++ using some easy and comprehensible example. Let’s say we have an array with n positive integers so, we have to find the minimum number of operations( addition, subtraction, multiplication, division ) done to make all the elements equal in the given array.

Minimum operations to make all elements equal in array


Approach
First of all, Let’s take any target value from the array so that we can make all the other ( n – 1 ) elements equal to that chosen value by doing operations on them. In this manner, all the elements will be equal to the targeted value in ( n – 1 ) operations which are maximum no. operations. But as our problem states that we have to find that minimum number of operations. To minimize the number of operation we have to find the most repeating element in an array so that we can choose that element our target value. To understand this better let’s take an example.

Array = { 10, 10, 2, 3, 10 }
Target Value = 10 ( because 10 has the maximum frequency)
So, we have to do one operation on 2 and one operation on 3 to make it equal to 10.
Min Operation = No. of elements in array - max frequency =  5 - 3 = 2

So, we have to do only ( N  –  max_frequency) operations to achieve the given task.

Time complexity:

  • O(n^2) { using iterative method}
  • O(n) {By using hashing}
  • O(nlogn) ( Sorting)

 

Here is the code :

#include <bits/stdc++.h> 
using namespace std; 

// function for min Operation 

int MinOperation (int arr[], int n) 
{ 
    int size = (*max_element(arr, arr + n)) + 1;
    
    int freq[size];

    for (int i=0;i<size;i++)
        freq[i] = 0;

    // update frequency of each element
    for (int i=0;i<n;i++)
        freq[arr[i]]++;

    
  // find the max frequency 
  int max_freq = *max_element(freq, freq + size) ;

  // return result 
  return (n - max_freq); 
} 

// main function 
int main() 
{ 
  int arr[] = {1, 8, 8, 5, 6, 1, 3, 2, 1, 3, 1}; 
  
  int n = sizeof(arr) / sizeof(arr[0]); 
  
  cout << "Minimum operation required :" << MinOperation(arr, n); 

  return 0; 
} 
Output Minimum operation required : 7

Hope this article was helpful to you. Keep Coding Keep Learning.

Also Read:

  1. Find all triplets with zero-sum in C++ (Hash Tables)

Leave a Reply

Your email address will not be published. Required fields are marked *