Problem Description
Alice has n candies, where the i-th candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor. The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice. Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.
Key Insights
- Alice can eat at most n / 2 candies.
- The aim is to maximize the number of different candy types consumed.
- The number of different types of candies is limited by the unique types present in the candyType array.
- The answer will be the lesser of the number of unique candy types and n / 2.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
To solve the problem, we will use a set data structure to track unique candy types. We will iterate through the candyType array, adding each type to the set. The maximum number of different types of candies Alice can eat will be the minimum of the size of the set (number of unique types) and n / 2 (the maximum candies she can consume).