Distribute Candies

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:

1. 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.

2. Determine the number of unique candy types available in the candyType array using a data structure like a set to filter out duplicates.

3. 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 of allowed 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.

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

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);
    }
}