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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int DistributeCandies(int[] candyType) {
6 HashSet<int> uniqueCandies = new HashSet<int>(candyType);
7 return Math.Min(uniqueCandies.Count, candyType.Length / 2);
8 }
9}This C# solution employs a HashSet to track unique candy types, then computes the result by taking the minimum between 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#include <vector>
using namespace std;
class Solution {
public:
int distributeCandies(vector<int>& candyType) {
unordered_map<int, int> candyMap;
for (int candy : candyType) {
candyMap[candy]++;
}
return min(candyMap.size(), candyType.size() / 2);
}
};The C++ implementation uses an unordered_map for easy frequency counting, comparing entry size to n / 2 for final decision.