Fair Distribution of Cookies

Medium
1348.

Fair Distribution of Cookies

Fair Distribution of Cookies is a medium coding problem on dynamic programming, bit manipulation and backtracking, asked in Amazon and Google interviews.

cookies[i] is the number of cookies in the i-th bag. Give every bag, unopened, to one of k children; a child may get several bags or none.

The unfairness of a distribution is the largest total number of cookies any single child receives.

Return the minimum unfairness over all distributions.

Example 1

Input
cookies = [4,7,3,6,2], k = 2
Output
11
Explanation
`[4,7]` and `[3,6,2]` both total 11.

Example 2

Input
cookies = [5,5,5,5], k = 2
Output
10

Example 3

Input
cookies = [9,1,2,3], k = 3
Output
9
Explanation
The bag of 9 alone already decides it: `[9]`, `[1,2]`, `[3]`.

Constraints

  • 2 <= cookies.length <= 8
  • 1 <= cookies[i] <= 10^5
  • 2 <= k <= cookies.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} cookies
 * @param {number} k
 * @return {number}
 */
var distributeCookies = function(cookies, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Fair Distribution of Cookies — Problem & Solution

Fair Distribution of Cookies solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Fair Distribution of Cookies is a medium coding problem on dynamic programming, bit manipulation and backtracking, asked in Amazon and Google interviews.

Problem statement

cookies[i] is the number of cookies in the i-th bag. Give every bag, unopened, to one of k children; a child may get several bags or none.

The unfairness of a distribution is the largest total number of cookies any single child receives.

Return the minimum unfairness over all distributions.

Example 1

Input: cookies = [4,7,3,6,2], k = 2
Output: 11
Explanation: `[4,7]` and `[3,6,2]` both total 11.

Example 2

Input: cookies = [5,5,5,5], k = 2
Output: 10

Example 3

Input: cookies = [9,1,2,3], k = 3
Output: 9
Explanation: The bag of 9 alone already decides it: `[9]`, `[1,2]`, `[3]`.

Constraints

  • 2 <= cookies.length <= 8
  • 1 <= cookies[i] <= 10^5
  • 2 <= k <= cookies.length

Hints for Fair Distribution of Cookies

  1. Hint 1

    With at most 8 bags, try every way to hand them out — but prune hard.

  2. Hint 2

    Assign bags one at a time to a child. Abandon a branch as soon as some child's total reaches the best unfairness found so far.

  3. Hint 3

    Children with nothing yet are interchangeable: when a bag goes to an empty child, trying a second empty child repeats the same distribution. Handing out the largest bags first makes the pruning bite early.

How to solve Fair Distribution of Cookies

The instance is tiny, so a backtracking search over "which child gets this bag" is exact; symmetry breaking (empty children are identical) and bounding by the best answer so far keep it fast.

Approach

  1. Sort the bags in descending order and keep sums[0..k-1], the children's totals, and best = infinity.
  2. dfs(i, curMax): if curMax >= best, return. If all bags are placed, set best = curMax.
  3. Otherwise, for each child j: add bag i to sums[j], recurse with max(curMax, sums[j]), then remove it. If sums[j] is 0 after removal (the child was empty), stop trying further children.
  4. Return best.

Why it works

Every distribution corresponds to a branch of the search, except that distributions differing only by a permutation of empty children are merged — they have identical unfairness, so nothing is lost. The bound prunes only branches whose unfairness can no longer drop below the best already found, since totals never decrease as more bags are added.

Complexity

  • Time — O(k^n) worst case, far less with pruning
  • Space — O(n + k)

Pitfalls

  • Without the empty-child symmetry break the search repeats each distribution up to k! times.
  • Giving every bag to the currently poorest child (greedy) is not optimal.
  • A child may receive no bags; do not force each child to get one.

Reference solution

Python

from typing import List

def distributeCookies(cookies: List[int], k: int) -> int:
    c = sorted(cookies, reverse=True)
    sums = [0] * k
    best = [1 << 30]

    def dfs(i, cur):
        if cur >= best[0]:
            return
        if i == len(c):
            best[0] = cur
            return
        for j in range(k):
            sums[j] += c[i]
            dfs(i + 1, max(cur, sums[j]))
            sums[j] -= c[i]
            if sums[j] == 0:
                break

    dfs(0, 0)
    return best[0]

Java

public static int distributeCookies(int[] cookies, int k) {
    int[] c = cookies.clone();
    Arrays.sort(c);
    for (int i = 0, j = c.length - 1; i < j; i++, j--) { int t = c[i]; c[i] = c[j]; c[j] = t; }
    int[] best = {1 << 30};
    dfcDfs(c, new int[k], 0, 0, best);
    return best[0];
}

static void dfcDfs(int[] c, int[] sums, int i, int cur, int[] best) {
    if (cur >= best[0]) return;
    if (i == c.length) { best[0] = cur; return; }
    for (int j = 0; j < sums.length; j++) {
        sums[j] += c[i];
        dfcDfs(c, sums, i + 1, Math.max(cur, sums[j]), best);
        sums[j] -= c[i];
        if (sums[j] == 0) break;
    }
}

C++

static void dfcDfs(const vector<int>& c, vector<int>& sums, int i, int cur, int& best) {
    if (cur >= best) return;
    if (i == (int)c.size()) { best = cur; return; }
    for (size_t j = 0; j < sums.size(); j++) {
        sums[j] += c[i];
        dfcDfs(c, sums, i + 1, max(cur, sums[j]), best);
        sums[j] -= c[i];
        if (sums[j] == 0) break;
    }
}

int distributeCookies(vector<int>& cookies, int k) {
    vector<int> c(cookies);
    sort(c.rbegin(), c.rend());
    vector<int> sums(k, 0);
    int best = 1 << 30;
    dfcDfs(c, sums, 0, 0, best);
    return best;
}

JavaScript

var distributeCookies = function(cookies, k) {
    var c = cookies.slice().sort(function(a, b) { return b - a; });
    var sums = new Array(k).fill(0), best = 1 << 30;
    function dfs(i, cur) {
        if (cur >= best) return;
        if (i === c.length) { best = cur; return; }
        for (var j = 0; j < k; j++) {
            sums[j] += c[i];
            dfs(i + 1, Math.max(cur, sums[j]));
            sums[j] -= c[i];
            if (sums[j] === 0) break;
        }
    }
    dfs(0, 0);
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Bit Manipulation