Maximum Candies Allocated to K Children - Practice Coding Problems

Maximum Candies Allocated to K Children - Problem

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can be allocated candies from only one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Input & Output

Example 1 — Basic Distribution

$ Input: candies = [5,8,6], k = 3

› Output: 5

💡 Note: We can give 5 candies to each child: pile[0] gives 1 child (5÷5=1), pile[1] gives 1 child (8÷5=1), pile[2] gives 1 child (6÷5=1). Total = 3 children ≥ 3.

Example 2 — Multiple Children Per Pile

$ Input: candies = [2,5], k = 11

› Output: 0

💡 Note: Maximum children we can satisfy is 2÷1 + 5÷1 = 7, which is less than 11. So each child gets 0 candies.

Example 3 — Optimal Split

$ Input: candies = [5,2,3], k = 4

› Output: 2

💡 Note: Give 2 candies each: pile[0] gives 2 children (5÷2=2), pile[1] gives 1 child (2÷2=1), pile[2] gives 1 child (3÷2=1). Total = 4 children.

Constraints

1 ≤ candies.length ≤ 10⁵
1 ≤ candies[i] ≤ 10⁷
1 ≤ k ≤ 10¹²

Visualization

Tap to expand

Understanding the Visualization

Input

Array of candy piles and number of children k

Process

Binary search for maximum candies per child

Output

Maximum candies each child can receive equally

Key Takeaway

🎯 Key Insight: Use binary search on answer space - if x candies work, then any amount < x also works

Asked in

G Google 12 a Amazon 8 M Microsoft 6 f Meta 4

The key insight is that this problem has a monotonic property: if we can give x candies to each child, we can also give any amount less than x. This makes it perfect for binary search on the answer space. Best approach is binary search with time O(n × log(max(candies))) and space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Linear Search	O(max(candies) × n)	O(1)	Try every possible candy count from 1 to maximum pile size
Binary Search on Answer	O(n × log(max(candies)))	O(1)	Binary search to find the maximum candies per child efficiently

Brute Force Linear Search — Algorithm Steps

Start from maximum pile size
For each candidate count, calculate total children possible
Return first count that satisfies k children

Visualization

Tap to expand

Step-by-Step Walkthrough

Start with max

Begin with largest pile size

Count children

For each candy count, calculate total children possible

Find first valid

Return first count that satisfies k children

Code -

solution.c — C

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

int solution(int* candies, int candiesSize, int k) {
    if (candiesSize == 0 || k == 0) return 0;
    
    int maxCandies = 0;
    for (int i = 0; i < candiesSize; i++) {
        if (candies[i] > maxCandies) {
            maxCandies = candies[i];
        }
    }
    
    // Try each possible candy count from max down to 1
    for (int candyCount = maxCandies; candyCount >= 1; candyCount--) {
        int totalChildren = 0;
        for (int i = 0; i < candiesSize; i++) {
            totalChildren += candies[i] / candyCount;
        }
        
        if (totalChildren >= k) {
            return candyCount;
        }
    }
    
    return 0;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int candies[1000];
    int candiesSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        candies[candiesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(candies, candiesSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(max(candies) × n)

For each possible candy count (up to max pile), we iterate through all n piles

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 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 Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler