Home » Data Structure » Hashing Coding Problems

# Minimum number of operations to make all elements same using hashing

Here, we are going to see how efficiently we can use a **hash table to find the minimum number of operations required to make all elements of the array same**?

Submitted by Radib Kar, on July 02, 2020

Prerequisite:

**Problem statement:**

Find the minimum number of operations required to make all elements the same. The possible operations are to add any number, delete any number, multiply with any number, and divide by any number.

**Example:**

Input array= [1, 2, 1, 1, 4, 5, 6] The minimum number of operations required is 4. Leave the 1s Subtract 1 from 2->1 operation Divide 4 by 4-> one operation Divide 5 by 5-> one operation Subtract 5 from 6-> one operation So the array is now [1, 1, 1, 1, 1, 1, 1] and minimum operation required is 4 One can come up with other operations too to convert the array in to same elements, but the minimum would be 4 and that's optimum.

**Solution:**

We can solve this problem using a hash map (hash table). One thing is clear that to achieve the minimum number of operation, we need to keep some elements unchanged and need to convert the rest of the elements to the unchanged element. So, which element should be kept as unchanged to achieve the minimum number of deletion? Of course, the element that has the highest number of occurrences should be kept and the rest of the elements will take one operation each to get converted into the unchanged element.

For example, In the above input, 1 has the most number of occurrences and that’s why we kept that unchanged and converted other elements into 1.

So our goal is to find the element which maximum occurrences and minimum number of operation required will be=n-max frequency where n is the total number of elements

So how can we design the problem with the hash table and what will be the hash function?

Okay, so here each element is our keys and the hash table has the size of the range of the array. So, if the range of the array is [0,99] then the hash table size would be 100.

What will be our hash function and how would we map the keys to the corresponding location in the hash table?

The hash function *h(x)=x* here but instead of storing the key itself using linear probing we will keep the count only as we require frequency for unique keys.

So, for example, if we have three 2s as our key, the hash table will store the count(frequency) at location 2.

So, after the hash table is created we can easily find the most occurred elements by each location (index) of the hash table.

So the algorithm will be,

**Step 1:**

Create the hash table like below: Initially hash table is empty For each key in input array: Hash[key]++

**Step 2:**

Initiallymax_freq=0For each location If(hash[location]>max_freq) Update max_freq as hash[location] After, thismax_freqcontains the number of occurrences for the most frequent key and the rest of the keys need to be deleted. So the minimum number of the operation:n-max_freqwhere,n= total number of keys/input elements

**Dry run with the example:**

Input array is = [1, 2, 1, 1, 4, 5, 6] So hash table size would be (6-1)=6 After creating the hash table as step1 we will have Index Value 1 3 2 1 4 1 5 1 6 1 So, max_freq = 3 Hence, minimum operations needed = 7-3 = 4

**C++ implementation:**

// C++ program to find the minimum operation // to make all elements equal in array #include <bits/stdc++.h> using namespace std; int minimum_operation(vector<int> arr, int n) { //create a hash table where for each key //the hash function is h(x)=x //we will use stl map as hash table //and will keep frequencies stored //so say two keys are mapping to the same location, //then the location will have value 2 //instead of the keys itself map<int, int> hash; //for each number for (auto i : arr) { hash[i]++; } //now to make all elements same we can //do four types of operation: //1. add any number //2. subtract any number //3. divide any number //4. multiply any number //we need to keep only the key with maximum frequency //we need to convert the other keys to //the key with maximum frequency //to convert any number to another number //we only require one operation //so find the key with max frequency int maxfreq = 0; for (auto it = hash.begin(); it != hash.end(); it++) { if (it->second > maxfreq) { maxfreq = it->second; } } //so minimum operation needed is: n-maxfreq return n - maxfreq; } int main() { int n; cout << "Enter number of elements\n"; cin >> n; vector<int> arr(n, 0); cout << "Input the array elements\n"; for (int i = 0; i < n; i++) { cin >> arr[i]; } cout << "Minimum number of operations required to make all elements same is: "; cout << minimum_operation(arr, n) << endl; return 0; }

**Output:**

Enter number of elements: 7 Input the array elements 1 2 1 1 4 5 6 Minimum number of operations required to make all elements same is: 4

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions