Distribute Candies — LeetCode 575 Python Solution

The problem

Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

Example

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.

Python solution

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        return min(len(candyType) >> 1, len(set(candyType)))

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 575. Distribute Candies is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems