Fair Distribution of Cookies - Practice Coding Problems

Fair Distribution of Cookies - Problem

You are given an integer array cookies, where cookies[i] denotes the number of cookies in the i-th bag. You are also given an integer k that denotes the number of children to distribute all the bags of cookies to.

All the cookies in the same bag must go to the same child and cannot be split up.

The unfairness of a distribution is defined as the maximum total cookies obtained by a single child in the distribution.

Return the minimum unfairness of all distributions.

Input & Output

Example 1 — Basic Distribution

$ Input: cookies = [8,15,10,20,8], k = 2

› Output: 31

💡 Note: Optimal distribution: Child 1 gets [8,15,8] = 31, Child 2 gets [10,20] = 30. Maximum is 31.

Example 2 — Equal Distribution

$ Input: cookies = [6,1,3,2,2,4,1,2], k = 3

› Output: 7

💡 Note: One optimal way: Child 1: [6,1] = 7, Child 2: [3,2,2] = 7, Child 3: [4,1,2] = 7. All children get 7 cookies.

Example 3 — Single Large Bag

$ Input: cookies = [1,1,1,1,20], k = 2

› Output: 20

💡 Note: Child 1 gets [1,1,1,1] = 4, Child 2 gets [20] = 20. The large bag determines the minimum unfairness.

Constraints

2 ≤ cookies.length ≤ 8
1 ≤ cookies[i] ≤ 10⁵
2 ≤ k ≤ cookies.length

Visualization

Tap to expand

Understanding the Visualization

Input

Cookie bags [8,15,10,20,8] and k=2 children

Distribute

Assign each bag to one of the children

Minimize Max

Find assignment that minimizes maximum cookies per child

Key Takeaway

🎯 Key Insight: Use backtracking with pruning to find the distribution that minimizes the maximum cookies any child receives

Asked in

G Google 25 a Amazon 18 f Facebook 15

The key insight is to use backtracking with aggressive pruning to explore all possible distributions while eliminating branches that cannot improve the answer. The optimized backtracking approach sorts bags in descending order, prunes branches when current maximum exceeds the best found, and avoids duplicate assignments to empty children. Time: O(k^n) with significant pruning, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(n * log(sum))	O(k)	Binary search on the unfairness value and check if distribution is feasible
Backtracking with Pruning	O(k^n)	O(n)	Enhanced backtracking with early termination and optimizations
Backtracking All Distributions	O(k^n)	O(n)	Try every possible way to assign cookie bags to children

Binary Search on Answer — Algorithm Steps

Binary search between 0 and sum of all cookies
For each mid value, check if distribution is feasible
Use greedy approach: assign bags to first child that can take them
If feasible, try smaller unfairness; otherwise try larger

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Space

Between max(cookies) and sum(cookies)

Test Mid

Check if mid value allows valid distribution

Narrow Range

Eliminate half the search space each iteration

Code -

solution.c — C

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

bool canDistribute(int* cookies, int n, int k, int maxUnfairness) {
    int* children = (int*)calloc(k, sizeof(int));
    for (int i = 0; i < n; i++) {
        bool assigned = false;
        for (int j = 0; j < k; j++) {
            if (children[j] + cookies[i] <= maxUnfairness) {
                children[j] += cookies[i];
                assigned = true;
                break;
            }
        }
        if (!assigned) {
            free(children);
            return false;
        }
    }
    free(children);
    return true;
}

int maxInArray(int* arr, int size) {
    int max = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

int sumArray(int* arr, int size) {
    int sum = 0;
    for (int i = 0; i < size; i++) {
        sum += arr[i];
    }
    return sum;
}

int solution(int* cookies, int n, int k) {
    int left = maxInArray(cookies, n);
    int right = sumArray(cookies, n);
    int result = right;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canDistribute(cookies, n, k, mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int cookies[20];
    int n = 0;
    char* ptr = line + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        cookies[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(cookies, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * log(sum))

Binary search on sum takes O(log(sum)) iterations, each with O(n) feasibility check

⚡ Linearithmic

Space Complexity

O(k)

Array to track children totals during feasibility check

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

856 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

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler