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.

Fewest Distinct Values to Delete At Least Half the Array

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

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.

Hints

1. Picking a value always removes every copy of it, so each distinct value can be summarized by how many times it occurs.
2. For a fixed number of picked values, ask which choice of values deletes the most elements.
3. Compare against the threshold in integers, as 2 * deleted >= n, so odd lengths need no rounding.

Approach

Only the occurrence count of each distinct value matters, because picking a value always deletes all of its copies. Count occurrences, sort the counts in non-increasing order, and take counts from the largest down while 2 * deleted < n; the number of counts taken is the answer. Invariant: after taking k counts, deleted equals the largest number of elements any k distinct values can delete, since the i-th largest count is at least the i-th count of any other k-value choice. So if the top k counts fall short of the threshold, every set of size k does too, and the first k whose top-k sum satisfies 2 * deleted >= n is the minimum. Ties among equal counts do not matter because only the sum is used. Edge cases: n = 1 needs one pick; an array of one repeated value needs one pick; odd n needs (n + 1) / 2 deletions, which the integer comparison 2 * deleted >= n handles without rounding, and a value with exactly n/2 copies in even n is enough on its own. Values in -10^9..10^9 are only compared for equality, never subtracted, so no overflow occurs.

• Time complexity: O(n log n)
• Space complexity: O(n)