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.
- Difficulty: Medium
- Topics: Dynamic Programming, Bit Manipulation, Backtracking, Bitmask
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 81 <= cookies[i] <= 10^52 <= k <= cookies.length
Hints for Fair Distribution of Cookies
Hint 1
With at most 8 bags, try every way to hand them out — but prune hard.
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.
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
- Sort the bags in descending order and keep
sums[0..k-1], the children's totals, andbest= infinity. dfs(i, curMax): ifcurMax >= best, return. If all bags are placed, setbest = curMax.- Otherwise, for each child
j: add bagitosums[j], recurse withmax(curMax, sums[j]), then remove it. Ifsums[j]is 0 after removal (the child was empty), stop trying further children. - 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