#575

Distribute Candies

pupil · 340 · lc easy +22 · verified · 70.8% accepted · 1,730 likes · top 80%

Description

Alice has n candies described by the array candyType, where candyType[i] is the type of the ith candy. Her doctor allows her to eat at most n / 2 candies (n is always even). To maximize variety, she wants to eat as many distinct types as possible within that limit. Return the maximum number of distinct candy types she can enjoy.

Example 1:

Input: candyType = [1,1,2,2,3,3]

Output: 3

Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.

Example 2:

Input: candyType = [1,1,2,3]

Output: 2

Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.

Example 3:

Input: candyType = [6,6,6,6]

Output: 1

Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.

Code

1

2

3

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int: