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.
1import java.util.HashSet;
2
3public class Solution {
4 public int distributeCandies(int[] candyType) {
5 HashSet<Integer> uniqueCandies = new HashSet<>();
6 for (int candy : candyType) {
7 uniqueCandies.add(candy);
8 }
9 return Math.min(uniqueCandies.size(), candyType.length / 2);
10 }
11}This Java solution uses a HashSet to find unique candy types, then returns the minimum of the number 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.
1using System.Collections.Generic;
public class Solution {
public int DistributeCandies(int[] candyType) {
Dictionary<int, int> candyMap = new Dictionary<int, int>();
foreach (var candy in candyType) {
if (!candyMap.ContainsKey(candy)) {
candyMap[candy] = 0;
}
candyMap[candy]++;
}
return Math.Min(candyMap.Count, candyType.Length / 2);
}
}C# solution with Dictionary to tabulate candy counts, checking count of keys versus n / 2 for the answer.