# 1338. Reduce Array Size to The Half

#### Medium

***

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:**

<pre><code>Input: arr = [3,3,3,3,5,5,5,2,2,7]
<strong>Output:
</strong> 2
<strong>Explanation:
</strong> Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.
</code></pre>

**Example 2:**

<pre><code>Input: arr = [7,7,7,7,7,7]
<strong>Output:
</strong> 1
<strong>Explanation:
</strong> The only possible set you can choose is {7}. This will make the new array empty.
</code></pre>

&#x20;

**Constraints:**

* `2 <= arr.length <= 105`
* `arr.length` is even.
* `1 <= arr[i] <= 105`

```python
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        #.
        n = len(arr)
        cnt = Counter(arr)

        counting = [0] * (n + 1)
        for freq in cnt.values():
            counting[freq] += 1

        ans, removed, half, freq = 0, 0, n // 2, n
        while removed < half:
            ans += 1
            while counting[freq] == 0: freq -= 1
            removed += freq
            counting[freq] -= 1
        return ans
```