Reduce Array Size to The Half
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 of the array are removed.
Example 1
Input
arr = [3,3,3,3,5,5,5,2,2,7]Output
2Choosing {3,7} makes the new array [5,5,5,2,2], whose size is exactly half of the original array, and no valid set of size 1 can remove at least half.
Example 2
Input
arr = [7,7,7,7,7,7]Output
1The only possible set is {7}, which removes all elements and makes the array empty.
Constraints
- 2 <= arr.length <= 10^5
- arr.length is even.
- 1 <= arr[i] <= 10^5