Fewest Distinct Values to Delete So at Least Half the Array Is Removed
Company: Microsoft
Role: Applied Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array `arr` of length `n`, pick a set of distinct values and delete every occurrence of each picked value from the array. A set is enough when the number of deleted elements is at least half of `n`. Return the smallest possible size of a set that is enough.
### Function Signature
```python
def min_values_to_remove_half(arr: list[int]) -> int:
```
### Rules
- Picking a value deletes all of its occurrences; you cannot delete only some copies of a value.
- "At least half" means `2 * deleted >= n`. For odd `n` this requires at least `(n + 1) / 2` deleted elements; for `n = 5`, at least 3.
- Return only the size of the set, which is a single integer.
### Constraints
- `1 <= len(arr) <= 10^5`
- `-10^9 <= arr[i] <= 10^9`
### Examples
**Example 1**
```text
Input: arr = [4, 4, 4, 7, 7, 2, 9, 9]
Output: 2
```
`n = 8`, so at least 4 elements must go. No single value occurs 4 or more times; picking `{4, 7}` deletes 5 elements.
**Example 2**
```text
Input: arr = [3, 3, 8, 8, 5]
Output: 2
```
`n = 5`, so at least 3 elements must go. Picking `3` alone deletes only 2 (`2 * 2 = 4 < 5`); picking `{3, 8}` deletes 4.
**Example 3**
```text
Input: arr = [1, 2, 3, 4, 5, 6]
Output: 3
```
Every value occurs once, so three values must be picked to delete 3 of the 6 elements.
Overview: A coding question that asks for the fewest distinct values whose complete deletion removes at least half of an integer array. It tests reasoning about how often each value occurs, proving that a choice is minimal, and the exact meaning of half when the array length is odd.
Read the full Microsoft Applied Scientist interview experience this question came from