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 <stdio.h>
2#include <stdlib.h>
3
4int cmpfunc(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int distributeCandies(int* candyType, int candyTypeSize) {
9 qsort(candyType, candyTypeSize, sizeof(int), cmpfunc);
10 int uniqueTypes = 1;
11 for (int i = 1; i < candyTypeSize; i++) {
12 if (candyType[i] != candyType[i - 1])
13 uniqueTypes++;
14 }
15 return (uniqueTypes < candyTypeSize / 2) ? uniqueTypes : candyTypeSize / 2;
16}The solution sorts the candy types to easily count unique types. After sorting, a single pass through the array determines the number of unique types. The result is the minimum between the 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 python solution uses Counter to determine frequency counts, which inherently provides unique element counts. The minimal value between this count and n / 2 determines how many types Alice can eat.