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
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.
### 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.
Every element fits in a signed 32-bit integer, and the answer is at most `n <= 10^5`, so no input or output value exceeds 2^31 - 1.
### Constraints
- `1 <= len(arr) <= 10^5`
- `-10^9 <= arr[i] <= 10^9`
- Duplicates are allowed.
### 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.
Constraints
- 1 <= len(arr) <= 10^5
- -10^9 <= arr[i] <= 10^9
- Duplicates are allowed.
Examples
Input: ([42],)
Expected Output: 1
Explanation: Singleton (minimum n = 1): picking its only value deletes 1 element and 2 * 1 >= 1.
Input: ([4, 4, 4, 7, 7, 2, 9, 9],)
Expected Output: 2
Explanation: Source Example 1: n = 8 needs 4 deletions; counts 3,2,2,1, so 3 alone falls short and 3 + 2 = 5 suffices.
Hints
- Picking a value always removes every copy of it, so each distinct value can be summarized by how many times it occurs.
- For a fixed number of picked values, ask which choice of values deletes the most elements.
- Compare against the threshold in integers, as 2 * deleted >= n, so odd lengths need no rounding.