Cross Out Half the List

Medium

You get a list of integers items of even length. You may pick some values and cross out every occurrence of each of them. What is the smallest number of values you need to pick so that at least half of the list's elements get crossed out?

Example 1

items=[4, 4, 4, 9, 9, 1, 1, 2] → 2

Out of 8 elements at least 4 must go. One value is not enough (the most frequent, 4, appears 3 times), while 4 and 9 together remove 5 elements. The answer is 2.

Example 2

items=[5, 6, 7, 8] → 2

All values differ, each one removes a single element, and two must be removed.

Example 3

items=[3, 3, 3, 3, 1, 2] → 1

Constraints

2 ≤ len(items) ≤ 10⁵
len(items) is even
1 ≤ items[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Hash Table Sorting Heap (Priority Queue)

Similar problems

Jobs With a Cooldown Medium Spread Out the Labels Medium Narrowest Range Touching Every List Hard Clearing the Stacks Evenly Easy Showcase: Profit Plus Variety Hard

Input

items=[4, 4, 4, 9, 9, 1, 1, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 64 tests on the server, hidden ones included.