Distribute Candies - Practice Coding Problems

Distribute Candies - Problem

Alice has n candies, where the i-th 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.

Input & Output

Example 1 — Basic Case

$ Input: candyType = [1,1,2,2,3,3]

› Output: 3

💡 Note: There are 3 unique candy types (1, 2, 3). Alice can eat 6/2 = 3 candies, so she can eat all 3 different types.

Example 2 — More Types Than Allowed

$ Input: candyType = [1,1,2,3]

› Output: 2

💡 Note: There are 3 unique types (1, 2, 3) but Alice can only eat 4/2 = 2 candies, so maximum variety is 2.

Example 3 — All Same Type

$ Input: candyType = [6,6,6,6]

› Output: 1

💡 Note: Only 1 unique type exists. Alice can eat 4/2 = 2 candies, but max variety is limited to 1 type.

Constraints

n == candyType.length
2 ≤ n ≤ 10⁴
n is even
-10⁵ ≤ candyType[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of candy types with duplicates

Constraints

Can eat n/2 candies, want max variety

Output

Maximum different types possible

Key Takeaway

🎯 Key Insight: The answer is always min(unique_types, n/2) - Alice is limited by either variety available or eating constraint

Asked in

F Facebook 15 a Amazon 10

The key insight is that Alice wants maximum variety but is limited by both unique types available and doctor's constraint of n/2 candies. Best approach uses a hash set to count unique types in O(n) time, then returns min(unique_types, n/2). Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Manual Type Counting	O(n²)	O(n)	Count unique candy types by comparing each candy with all others
Hash Set - Optimal Unique Counting	O(n)	O(n)	Use a hash set to efficiently count unique candy types in one pass

Brute Force - Manual Type Counting — Algorithm Steps

For each candy, check if its type already exists in our unique list
If new type, add to unique list
Return minimum of unique types count and n/2

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Each Candy

Compare each candy with all previously found unique types

Build Unique List

Add new types to our unique types collection

Calculate Result

Return min(unique_count, n/2)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* candyType, int candyTypeSize) {
    int uniqueTypes[candyTypeSize];
    int uniqueCount = 0;
    
    for (int i = 0; i < candyTypeSize; i++) {
        int isUnique = 1;
        for (int j = 0; j < uniqueCount; j++) {
            if (uniqueTypes[j] == candyType[i]) {
                isUnique = 0;
                break;
            }
        }
        if (isUnique) {
            uniqueTypes[uniqueCount++] = candyType[i];
        }
    }
    
    return uniqueCount < candyTypeSize / 2 ? uniqueCount : candyTypeSize / 2;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int candyType[1000];
    int size = 0;
    char *token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        candyType[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(candyType, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n candies, we scan through all previous candies to check uniqueness

⚠ Quadratic Growth

Space Complexity

O(n)

In worst case, we store all n unique candy types in our tracking array

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Manual Type Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler