Solution: Distribute Candies
Tags: algorithms, javascript, java, python
Published: 2021-03-01 09:10:03

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/distribute-candies/discuss/1087842).*

---

#### [Leetcode Problem #575 (*Easy*): Distribute Candies](https://leetcode.com/problems/distribute-candies/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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.<br>Since there are only 3 types,<br>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.<br>Whether she eats types [1,2], [1,3], or [2,3],<br>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.<br>Even though she can eat 2 candies,<br>she only has 1 type.

---

#### ***Constraints:***
>
 - `n == candyType.length`
 - `1 <= n <= 10^4`
 - `n` is even.
 - `-10^5 <= candyType[i] <= 10^5`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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 **int**s into **Integer**s before converting to a **HashSet**, so it's easier just to build the **HashSet** iteratively via a **for loop**.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
const distributeCandies = C => Math.min((new Set(C)).size, C.length / 2)
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def distributeCandies(self, C: List[int]) -> int:
        return min(len(set(C)), len(C) // 2)
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int distributeCandies(vector<int>& C) {
        unordered_set<int> cset(begin(C), end(C));
        return min(cset.size(), C.size() / 2);
    }
};
```