#1338

Reduce Array Size to The Half

pupil · 570 · lc medium +29 · verified · 69.4% accepted · 3,362 likes · top 77%

Description

Given the integer array arr, select a subset of distinct values and remove every occurrence of those values from arr. Return the smallest possible subset size such that at least half of arr's elements are eliminated.

Example 1:

Input: arr = [3,3,3,3,5,5,5,2,2,7]

Output: 2

Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).

Possible sets of size 2 are {3,5},{3,2},{5,2}.

Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

Example 2:

Input: arr = [7,7,7,7,7,7]

Output: 1

Explanation: The only possible set you can choose is {7}. This will make the new array empty.

Code

1

2

3

class Solution:
    def minSetSize(self, arr: List[int]) -> int:

class Solution:
    def minSetSize(self, arr: List[int]) -> int: