Sponsored
Sponsored
The goal is to find the maximum number of unique types of candies Alice can eat. We can take the following steps:
maxCandies = n / 2.maxCandies.Time Complexity: O(n) because we iterate over the array to create the set.
Space Complexity: O(n) for storing the unique types in a set.
1#include <unordered_set>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 int distributeCandies(vector<int>& candyType) {
8 unordered_set<int> uniqueCandies(candyType.begin(), candyType.end());
9 return min(uniqueCandies.size(), candyType.size() / 2);
10 }
11};This C++ solution uses an unordered_set to count unique candy types, as it provides average constant time complexity for inserts. The result is the smallest among the size of unique types and n / 2.
For another perspective:
n / 2.Time Complexity: O(n) for creating the counter.
Space Complexity: O(n) for storing unique types in the counter.
1
This C solution uses an array as a frequency map, utilizing offsets for negative candy IDs. The unique count and check against n / 2 determine the result.