Description
You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array. Return the minimum size of the set so that at least half of the integers are removed.
Examples
Input:
arr = [3,3,3,3,5,5,5,2,2,7]Output:
2Explanation:
Remove 3 and 5 (8 of 10 removed).
Input:
arr = [1,1,2,2,3,3]Output:
3Explanation:
All elements appear exactly twice. To remove at least half (3 elements), the task requires remove all occurrences of 3 different numbers, requiring a set of size 3.
Input:
arr = [9,9,9,9,9,9,4,4]Output:
1Explanation:
Element 9 appears 6 times and element 4 appears 2 times. Since the task requires remove at least 4 elements (half of 8), it is possible to just remove all occurrences of 9, which removes 6 elements. This requires only 1 number in our set.
Constraints
- •
2 ≤ arr.length ≤ 10^5 - •
arr.length is even