Problem statement

Alice has n candies, where candyType[i] is the type of the i-th candy. Her doctor tells her she may eat only n / 2 of them (n is even).

Alice wants to eat as many different types as she can while respecting the limit. Return the maximum number of distinct types she can eat.

Example 1

Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: She may eat 3 candies and there are 3 types, so she can have one of each.

Example 2

Input: candyType = [1,1,2,3]
Output: 2
Explanation: She may eat 2 candies; picking two different types gives 2.

Example 3

Input: candyType = [6,6,6,6]
Output: 1
Explanation: Only one type exists.

Constraints

• 2 <= candyType.length <= 40
• candyType.length is even.
• -100 <= candyType[i] <= 100

Hints for Distribute Candies

1. Hint 1

   She can never eat more than n / 2 candies, and never more distinct types than exist.

2. Hint 2

   The answer is the smaller of those two numbers.

3. Hint 3

   A hash set gives the number of distinct types in one pass.

How to solve Distribute Candies

She is capped by both the allowance n / 2 and the number of distinct types; the answer is the smaller of the two.

Approach

1. Count distinct types with a set.
2. Return min(distinct, n / 2).

Why it works

If there are at least n / 2 types she can pick one candy of n / 2 different types; otherwise she can take one of each type and still be under the limit.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• n is even by the constraints; integer division is exact.

Reference solution

Python

def distributeCandies(candyType):
    return min(len(set(candyType)), len(candyType) // 2)

Java

public static int distributeCandies(int[] candyType) {
    Set<Integer> seen = new HashSet<>();
    for (int x : candyType) seen.add(x);
    return Math.min(seen.size(), candyType.length / 2);
}

C++

int distributeCandies(vector<int>& candyType) {
    unordered_set<int> seen(candyType.begin(), candyType.end());
    return min((int) seen.size(), (int) candyType.size() / 2);
}

JavaScript

var distributeCandies = function(candyType) {
    const types = new Set(candyType).size;
    const half = candyType.length / 2;
    return types < half ? types : half;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy