
Problem Statement
Alice has a collection of n
candies, each identified by a type candyType[i]
. Due to health concerns, specifically weight gain, her doctor has advised her to limit her consumption to half of her candies, where n
is always an even number. Given her love for variety, Alice would like to maximize the number of different candy types she can enjoy within this limit. The task is to determine the maximum variety of candies Alice can consume, where she is only allowed to eat n / 2
candies out of her total collection.
Examples
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 <= 104
n
is even.-105 <= candyType[i] <= 105
Approach and Intuition
To solve this problem, we need to consider the following points:
Calculate half of the total number of candies:
allowed = n / 2
. This represents the maximum number of candies Alice is allowed to eat according to the doctor's advice.Determine the number of unique candy types available in the
candyType
array using a data structure like a set to filter out duplicates.Compare the number of unique candy types with
allowed
.- If the number of unique types is greater than or equal to
allowed
, then Alice can consume candies ofallowed
different types. - If the number of unique types is less than
allowed
, then Alice's variety is limited to the number of unique types available.
- If the number of unique types is greater than or equal to
Let's go through the examples to clarify these steps:
For
candyType = [1,1,2,2,3,3]
:- Allowed = 3 (since n = 6)
- Unique types = {1, 2, 3} (count of unique types = 3)
- Maximum different types she can eat = 3 (equal to allowed)
For
candyType = [1,1,2,3]
:- Allowed = 2 (since n = 4)
- Unique types = {1, 2, 3} (count of unique types = 3)
- Maximum different types she can eat = 2 (since allowed is less than unique types)
For
candyType = [6,6,6,6]
:- Allowed = 2 (since n = 4)
- Unique types = {6} (count of unique types = 1)
- Maximum different types she can eat = 1 (there's only one type)
From these observations and the problem's constraints, we can model our solution to first count the unique candy types, then simply return the minimum of allowed
and the count of unique types to get the maximum variety of candies Alice can eat.
Solutions
- Java
- Python
class Solution {
public int maxCandiesAllowed(int[] candies) {
HashSet<Integer> candySet = new HashSet<>();
for (int type : candies) {
candySet.add(type);
}
return Math.min(candySet.size(), candies.length / 2);
}
}
The provided Java solution focuses on determining the maximum number of different types of candies one can have from an array where each integer represents a type of candy. Firstly, the solution utilizes a HashSet to record unique candy types from the input array. Since a HashSet does not allow duplicate entries, it automatically retains only unique candy types.
The key part of the solution lies in the calculation:
Math.min(candySet.size(), candies.length / 2)
This line determines the maximum number of types a person can have by choosing the lesser value between the unique types available (candySet.size()
) and half of the total number of candies (candies.length / 2
). The division by two enforces a constraint where at most half of the candies can be chosen. This approach ensures that the selection of candies meets the requirement of both maximizing the variety and abiding by the allowed quantity.
In summary, the solution efficiently calculates the maximum number of different candy types one can possess by evaluating the smaller between the number of unique candy types and half the total number of candies given.
class Solution:
def maxCandies(self, types: List[int]) -> int:
# Calculate the number of unique types using set.
num_unique_types = len(set(types))
# Compute the maximum candies one can eat.
return min(num_unique_types, len(types) // 2)
This Python program addresses the problem of distributing candies evenly. It is designed to figure out how many different kinds of candies a person can eat given an array of candy types, where the goal is to maximize the variety of candies one can have, yet not exceed half the total number of candies.
- This program defines a method
maxCandies
that takes a list of integers,types
, representing candy types. - Convert the list to a set to determine the number of unique candy types.
- Return the minimum value between the number of unique candy types and half the total number of candies. This ensures not exceeding the allowed maximum while maximizing the variety.
No comments yet.