Solution: Distribute Candies

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #575 (Easy): Distribute Candies

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

---

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
• 1 <= n <= 10^4
• n is even.
• -10^5 <= candyType[i] <= 10^5

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

In order to solve this problem, we need to identify how many unique types of candy there are. The easiest method to find unique values is with a set. If we convert our input array of candy types (C) to a set, then it will only contain unique values, and thus the size of the set will represent the number of different candy types.

The only other thing to remember is that we're constrained to at most C.length / 2 pieces, per the instructions, so we need to use a min() boundary before we return our answer.

---

Implementation:

Java alone does not have an easy set constructor from an int array. Any such solution would have to invole boxing the primitive ints into Integers before converting to a HashSet, so it's easier just to build the HashSet iteratively via a for loop.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

const distributeCandies = C => Math.min((new Set(C)).size, C.length / 2)

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def distributeCandies(self, C: List[int]) -> int:
        return min(len(set(C)), len(C) // 2)

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int distributeCandies(int[] C) {
        Set<Integer> cset = new HashSet<>();
        for (int c : C) cset.add(c)
        return Math.min(cset.size(), C.length / 2);
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int distributeCandies(vector<int>& C) {
        unordered_set<int> cset(begin(C), end(C));
        return min(cset.size(), C.size() / 2);
    }
};