Fewest Distinct Values to Delete So at Least Half the Array Is Removed

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

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

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

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

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.