Author: Sanket Poojari
All Tutorials of Hashing are listed here: https://www.desiqna.in/tag/hashing_tutorials
It is recommended to go through previous hashing tutorials to get a better understanding..
Part 6: Minimum operations to make all elements equal in an array.
Given an array consisting of positive integers, return the minimum number of operations to make all the elements of the array equal. The operations can be addition, multiplication, division, or subtraction.
Example:
Input: arr[] = {1, 2, 3, 4}
Output: 3
(Since all the elements in the array are unequal, it would require at least 3 operations to make the array equal).
Logic:
In order to make all the elements equal, we will be selecting a value from the array(the target element) and converting the rest of the elements into the selected element. Now, how should we be selecting the target element? The target element will be the element that has the highest frequency in the array.
Let's say the element with the highest frequency occurs k times. Thus, we would require at least n-k operations for making all the array elements equal. Here n is the size of the array.
Approach 1: Brute-Force:
To find the element with the highest frequency, we will run two loops. The outer loop picks all the elements one by one and the inner loop finds the frequency of the picked element and compares it with the element with the highest frequency so far. If it is greater, it replaces to be the highest frequent element. After this, we will simply return the "number of elements - frequency of the most frequent element".
Time complexity: O(n2)
Space complexity: O(1)
Code (C++) :-
Approach 2: Hashing Approach
We can minimize the work done in the above approach by using a hash map. A hash map is nothing but a map that consists of the frequency of all the elements in the array. The highest frequent element in the hash table will be our target element and thus, our answer will be "number of elements - frequency of the target element".
Consider an array {1 , 2, 1, 4, 3, 1}.
First, we map the elements with their frequency:
As we can see, the element "1" has the highest frequency of 3, and this element will be our target element. Therefore, our answer will be,
Number of elements - Frequency of 1 = 6 - 3 = 3.
Time complexity: O(n)
Space complexity: O(n)
Code (C++) :-
Java https://ideone.com/1ym7z7
Python https://ideone.com/alQ1Hu