575. Distribute Candies
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 0
Acceptance rate: 64.4%
Problem Breakdown
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.
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.
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.
Constraints:
n == candyType.length
2 <= n <= 10^4
n is even.
-10^5 <= candyType[i] <= 10^5
Intuition
The brute-force approach would involve checking all possible combinations of n / 2 candies and counting the unique types in each combination. This approach is computationally expensive with a time complexity of O(2^(n/2)), which is infeasible given the constraints.
A better approach involves leveraging the properties of sets to determine the number of distinct candy types. The key insight is that Alice can eat at most min(n / 2, unique_candy_types) candies, where unique_candy_types is the number of different types of candies available.
Approach
- Count Unique Candy Types: Use a set to count the number of unique candy types in the array.
- Determine Maximum Candies Alice Can Eat: Calculate the minimum between half the total number of candies (
n / 2) and the number of unique candy types. - Return Result: The result is the maximum number of different types of candies Alice can eat.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the
candyTypearray. This is because we need to iterate through the array to populate the set. - Space Complexity: O(n) in the worst case, where all candy types are unique and stored in the set.
Solution
def distributeCandies(candyType):
# Step 1: Count unique candy types using a set
unique_candies = len(set(candyType))
# Step 2: Determine the maximum number of different types Alice can eat
max_candies_alice_can_eat = min(len(candyType) // 2, unique_candies)
# Step 3: Return the result
return max_candies_alice_can_eat
Edge Cases Handled
- All Candies of Same Type: If all candies are of the same type, the set will have only one element, and Alice can eat at most one type.
- Distinct Types Less Than Half Total Candies: If the number of distinct types is less than or equal to half the total number of candies, Alice can eat all distinct types.
- Large Input Size: The solution efficiently handles large input sizes up to
10^4due to linear time complexity.