Find Minimum delete operations to make all elements of array same in C++

In this tutorial, we are going to learn how to find the minimum delete operations needed to make all elements of an array the same in C++. Here we will see the algorithm and after that, we will see the C++ program for the same.

Let’s see an example first:-
You have given an array arr. You have to find the minimum delete operations needed to make all the elements the same.

Input:-
arr [ ] ={ 1 , 2 , 1 , 4 , 6 , 1 , 2 , 1 , 5 , 8 , 1 }

Output:-
The minimum operation needed = 6

Algorithm

We can find the minimum deletion operations by calculating the maximum occurrence of an element in the given array. And, subtracting that from the size of the given array.
For finding the maximum occurrence of an element of the array we use hashmap i.e unordered_map. Through unoredered_map we can find the occurrence of each element in O(n) time. Simultaneously, we find the maximum occurrence and subtract that from the size of the array to get the result.

Algorithm:-

1. Initialize an unordered_map
2. Using a single for loop, calculate the occurrences of each element of the array.
3. Simultaneously, calculate the max occurrence.
4. Subtract the max occurrence from size of array.
5. Print the output.

C++ Program for finding minimum delete operation to make all elements same

So, here is the C++ implementation of the above algorithm:-

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


/*===========================================
   FUNCTION TO FIND MINIMUM DEL OPERATIONS
============================================*/
void del_operations(int arr[],int n) 
{ 
  int i,ans=0;
  unordered_map<int,int>umap;
  //Loop for calculating occurences of each element
  for (i = 0; i <n; i++) 
  {
    umap[arr[i]]++;
    ans=max(ans,umap[arr[i]]);
  } 
    
  cout<<"Minimum operations needed = "<<n-ans<<endl; 
  
} 

/*===========================================
                MAIN FUNCTION
============================================*/ 
int main() 
{ 
  int arr[ ]={1,2,1,4,6,1,2,1,5,8,1};
  int n=sizeof(arr)/sizeof(arr[0]);
  del_operations(arr,n); 
  return 0; 
} 

Output:-

Minimum operations needed = 6

Thanks for reading this tutorial. I hope it helps you !!

Leave a Reply

Your email address will not be published.