Last Updated: 8 Apr, 2021
Reduce Array Size to The Half
Easy
Asked in company
Your friend gifted you ‘N’ balls. Each ball has a number associated with it, the numbers associated with the balls are given in the array 'ARR'. But your cupboard has slots such that only N/2 balls can be kept. So, you decided to remove the balls following an operation.
In one operation, you can select a ball numbered ‘x’ and remove all the balls which are numbered ‘x’.
You are supposed to minimize the number of operations such that at least half of the balls are removed from ‘N’ balls.
Note:
Numbers on the balls may not be unique.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.
The first line contains integer ‘N’, which denotes the number of elements in the array ‘ARR’.
The second line contains N integers denoting the elements of the array ‘ARR’.
Output Format:
For each test case, return the minimum number of operations you need to perform to remove at least half of the balls.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1<= T <= 50
1 <= N <= 10^4
N is always even.
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
Approaches
The idea is to traverse the array and count the number of occurrences and store it in a hashmap. After that traverse in the hashmap and sort the elements in descending order of their occurrences. Then delete the element which has the occurs maximum number of times, then the second maximum, etc until at least n/2 elements are not deleted.
The steps are as follows:
- Declare a hashmap 'COUNT_OCCURENCES' which stores the number associated with the balls as the key and their occurrences as the values.
- Iterate over the array 'ARR':
- If the current element is 'CURRENT', increment the count of 'CURRENT' in the hashMap 'COUNT_OCCURENCES'.
- Declare an array 'DESCENDING_OCCURENCES' that stores the occurrences of elements in descending order.
- Iterate over the hashmap 'COUNT_OCCURENCES':
- Push the number of occurrences of the current element in the array 'DESCENDING_OCCURENCES'.
- Sort the array 'DESCENDING_OCCURENCES' in descending order.
- Initialize two integers 'ANS', and 'REMOVED' to 0 which denotes the final answer and the number of elements that we removed.
- Iterate over the array 'DESCENDING_OCCURENCES':
- Add the current element into 'REMOVED' and increment 'ANS' by 1.
- If 'REMOVED' becomes greater than N/2, return the 'ANS' as the final answer.