Distribute Candies

easy hash set greedy

Problem

Alice has n candies of various kinds. She must give half away. Maximize how many different kinds she keeps.

InputcandyType = [1,1,2,2,3,3]

Output3

She keeps n/2=3 candies; there are 3 distinct kinds.

input

def distribute_candies(t):
    return min(len(set(t)), len(t) // 2)

function distributeCandies(t) {
  return Math.min(new Set(t).size, t.length / 2);
}

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

int distributeCandies(vector& t) {
    unordered_set s(t.begin(), t.end());
    return min((int)s.size(), (int)t.size() / 2);
}

Explanation

Alice must give away half her candies, so she gets to keep exactly n / 2 of them. The goal is to make those kept candies cover as many different kinds as possible.

There are two limits at play. She can never keep more than n / 2 candies total, and she can never keep more distinct kinds than actually exist. The answer is simply the smaller of those two numbers.

To count the distinct kinds, we drop every candy type into a hash set, which automatically discards duplicates. The set's size is the number of unique kinds. Then we return min(unique kinds, n / 2).

Example: candyType = [1,1,2,2,3,3]. Here n = 6 so she keeps 3. The set is {1, 2, 3}, giving 3 unique kinds. The answer is min(3, 3) = 3.

If there were many more kinds than half the candies, the n / 2 cap would win instead, since she physically cannot hold more than half.

Time: O(n) Space: O(n)