Fair Distribution of Cookies
MedPrompt
You are given an integer array cookies, where cookies[i] denotes the number of cookies in the ith 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.
Example 1:
Input: cookies = [8,15,10,20,8], k = 2
Output: 31
Explanation: One optimal distribution is [8,15,8] and [10,20]
- The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies.
- The 2nd child receives [10,20] which has a total of 10 + 20 = 30 cookies.
The unfairness of the distribution is max(31,30) = 31.
It can be shown that there is no distribution with an unfairness less than 31.Example 2:
Input: cookies = [6,1,3,2,2,4,1,2], k = 3
Output: 7
Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2]
- The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies.
- The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies.
- The 3rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies.
The unfairness of the distribution is max(7,7,7) = 7.
It can be shown that there is no distribution with an unfairness less than 7.
Constraints:
2 <= cookies.length <= 81 <= cookies[i] <= 1052 <= k <= cookies.length
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward approach that explores every possible distribution of cookie bags to the k children. It uses a recursive function that, for each cookie bag, tries assigning it to every child and then moves to the next bag. When all bags are distributed, it calculates the unfairness and updates the minimum unfairness found so far.
Algorithm
-
- Initialize a global variable
minUnfairnessto a very large value (e.g.,Integer.MAX_VALUE).
- Initialize a global variable
-
- Create an integer array
distributionof sizek, initialized to all zeros, to keep track of the cookies assigned to each child.
- Create an integer array
-
- Define a recursive function
backtrack(cookieIndex, distribution).
- Define a recursive function
-
- Base Case: If
cookieIndexequalscookies.length, all bags have been distributed. Calculate the maximum value in thedistributionarray. This is the unfairness for the current distribution. UpdateminUnfairness = min(minUnfairness, currentUnfairness)and return.
- Base Case: If
-
- Recursive Step: For the cookie bag at
cookieIndex, iterate through each childifrom0tok-1.
- Recursive Step: For the cookie bag at
-
- In the loop, add
cookies[cookieIndex]todistribution[i]to assign the bag to childi.
- In the loop, add
-
- Make a recursive call for the next cookie bag:
backtrack(cookieIndex + 1, distribution).
- Make a recursive call for the next cookie bag:
-
- After the recursive call returns, subtract
cookies[cookieIndex]fromdistribution[i]. This is the "backtracking" step, which undoes the choice to explore other possibilities.
- After the recursive call returns, subtract
-
- To start the process, call
backtrack(0, new int[k])from the main function.
- To start the process, call
-
- After the initial call completes,
minUnfairnesswill hold the minimum possible unfairness.
- After the initial call completes,
Walkthrough
We define a recursive function, say backtrack(cookieIndex, distribution), where cookieIndex is the index of the current cookie bag to be distributed, and distribution is an array of size k storing the current total cookies for each child.
The base case for the recursion is when cookieIndex reaches cookies.length. At this point, we have a complete distribution. We find the maximum value in the distribution array (the unfairness) and compare it with a global minimum, updating it if the current distribution is better.
In the recursive step, we iterate from i = 0 to k-1. For each child i, we tentatively assign cookies[cookieIndex] to them (by adding to distribution[i]), make a recursive call for the next cookie (cookieIndex + 1), and then backtrack by undoing the assignment (subtracting cookies[cookieIndex] from distribution[i]).
The process starts with backtrack(0, new int[k]).
class Solution { int minUnfairness = Integer.MAX_VALUE; public int distributeCookies(int[] cookies, int k) { backtrack(0, cookies, new int[k]); return minUnfairness; } private void backtrack(int cookieIndex, int[] cookies, int[] distribution) { if (cookieIndex == cookies.length) { int currentMax = 0; for (int sum : distribution) { currentMax = Math.max(currentMax, sum); } minUnfairness = Math.min(minUnfairness, currentMax); return; } for (int i = 0; i < distribution.length; i++) { distribution[i] += cookies[cookieIndex]; backtrack(cookieIndex + 1, cookies, distribution); distribution[i] -= cookies[cookieIndex]; // Backtrack } }}Complexity
Time
O(k^n), where `n` is the number of cookie bags and `k` is the number of children. For each of the `n` bags, there are `k` choices of which child to give it to, leading to `k^n` possible distributions in the recursion tree.
Space
O(n + k), where `n` is the number of cookie bags and `k` is the number of children. This is for the recursion stack depth (`O(n)`) and the `distribution` array (`O(k)`).
Trade-offs
Pros
Simple to understand and implement.
Correctly explores the entire search space to guarantee the optimal solution.
Cons
Highly inefficient due to its exponential time complexity.
Explores many redundant and symmetric states, making it too slow for the given constraints without timing out on some platforms.
This approach significantly improves upon the brute-force method by adding several key optimizations to the backtracking algorithm. These optimizations reduce the search space by avoiding redundant calculations and cutting off unpromising paths early.
Algorithm
-
- Initialize
minUnfairnessto a very large value.
- Initialize
-
- Sort the
cookiesarray in descending order. This is a heuristic that helps pruning to be more effective.
- Sort the
-
- Define a recursive function
backtrack(cookieIndex, distribution).
- Define a recursive function
-
- Base Case: If
cookieIndex == cookies.length, all bags are distributed. Calculate the maximum of thedistributionarray and updateminUnfairness.
- Base Case: If
-
- Recursive Step: For the current cookie
cookies[cookieIndex], loop through all childrenifrom0tok-1.
- Recursive Step: For the current cookie
-
- Pruning: Before assigning the cookie, check if
distribution[i] + cookies[cookieIndex] >= minUnfairness. If it is, this path cannot lead to a better solution, socontinueto the next child.
- Pruning: Before assigning the cookie, check if
-
- Assign the cookie:
distribution[i] += cookies[cookieIndex].
- Assign the cookie:
-
- Recurse:
backtrack(cookieIndex + 1, distribution).
- Recurse:
-
- Backtrack:
distribution[i] -= cookies[cookieIndex].
- Backtrack:
-
- Symmetry Breaking: After backtracking, if
distribution[i]is now0, it means we have fully explored the path of givingcookies[cookieIndex]to a previously empty-handed child. To avoid symmetric states, we canbreakthe loop, as giving this cookie to any other empty-handed child is an equivalent scenario.
- Symmetry Breaking: After backtracking, if
-
- Start the process by calling
backtrack(0, new int[k]).
- Start the process by calling
Walkthrough
The core idea is still backtracking, but we add pruning and symmetry-breaking techniques.
- 1. Pruning: If at any point, a child's current cookie sum
distribution[i]plus the current cookiecookies[cookieIndex]is already greater than or equal to the bestminUnfairnessfound so far, we can prune this entire branch of the recursion. This path cannot possibly lead to a better solution. - 2. Sorting: Sorting the
cookiesarray in descending order makes the pruning more effective. By assigning larger cookies first, we are more likely to hit theminUnfairnessbound early, allowing for more aggressive pruning. - 3. Symmetry Breaking: If we are assigning a cookie to a child who currently has zero cookies, it doesn't matter which empty-handed child we choose. They are all equivalent. To avoid exploring these symmetric states, we can enforce a rule: if we assign a cookie to an empty-handed child and that recursive path is fully explored, we don't need to try assigning the same cookie to other empty-handed children. This can be implemented by breaking the loop over children after backtracking from the first child with a sum of 0.
class Solution { int minUnfairness = Integer.MAX_VALUE; public int distributeCookies(int[] cookies, int k) { // Sorting in descending order is a good heuristic for pruning Arrays.sort(cookies); reverse(cookies); backtrack(0, cookies, new int[k], k); return minUnfairness; } private void backtrack(int cookieIndex, int[] cookies, int[] distribution, int k) { if (cookieIndex == cookies.length) { int currentMax = 0; for (int sum : distribution) { currentMax = Math.max(currentMax, sum); } minUnfairness = Math.min(minUnfairness, currentMax); return; } for (int i = 0; i < k; i++) { // Pruning if (distribution[i] + cookies[cookieIndex] >= minUnfairness) { continue; } distribution[i] += cookies[cookieIndex]; backtrack(cookieIndex + 1, cookies, distribution, k); distribution[i] -= cookies[cookieIndex]; // Backtrack // Symmetry Breaking if (distribution[i] == 0) { break; } } } private void reverse(int[] arr) { int i = 0, j = arr.length - 1; while (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } }}Complexity
Time
The worst-case complexity is still exponential, but significantly faster in practice than brute-force. The number of states explored is related to partitioning `n` items into `k` groups (described by Stirling numbers of the second kind), which is much smaller than `k^n`.
Space
O(n + k) for the recursion depth (`O(n)`) and the `distribution` array (`O(k)`).
Trade-offs
Pros
Much more efficient than the naive approach.
Pruning and symmetry breaking drastically reduce the search space, making it feasible for the given constraints.
Cons
The logic for optimizations, especially symmetry breaking, can be subtle to implement correctly.
The worst-case time complexity remains exponential, although it performs much better on average.
This advanced approach transforms the problem. Instead of searching for the minimum unfairness value directly, we binary search for it. For any given value x, we can determine if it's possible to achieve an unfairness of at most x. This decision problem ("is it possible?") can be solved efficiently with a pruned backtracking search.
Algorithm
-
- Define a search range for the answer. Let
lowbe the largest cookie value andhighbe the sum of all cookies.
- Define a search range for the answer. Let
-
- Perform a binary search in the range
[low, high].
- Perform a binary search in the range
-
- In each iteration, calculate
mid = low + (high - low) / 2.midis our candidate for the minimum unfairness.
- In each iteration, calculate
-
- Call a helper function
canDistribute(mid)that returnstrueif a distribution with unfairness at mostmidis possible, andfalseotherwise.
- Call a helper function
-
- The
canDistribute(mid)function uses a pruned backtracking search. It tries to distribute all cookies such that no child's sum exceedsmid. It should also use optimizations like sorting and symmetry breaking for efficiency.
- The
-
- If
canDistribute(mid)returnstrue, it meansmidis a possible answer. We try for an even better (smaller) one by settingans = midandhigh = mid - 1.
- If
-
- If
canDistribute(mid)returnsfalse,midis too small to be a valid unfairness. We must allow a larger value, so we setlow = mid + 1.
- If
-
- The loop continues until
low > high, and the finalansis the minimum unfairness.
- The loop continues until
Walkthrough
The possible values for the minimum unfairness lie in a range. The lower bound is the largest single cookie bag, and the upper bound is the sum of all cookies. We can binary search within this range.
For each mid value in our binary search, we call a function canDistribute(mid). This function returns true if there exists a distribution where no child gets more than mid cookies, and false otherwise.
- If
canDistribute(mid)istrue, it meansmidis a possible unfairness, so we try for a smaller value by settinghigh = mid - 1and storingmidas a potential answer. - If
canDistribute(mid)isfalse,midis too small, so we must allow a larger unfairness by settinglow = mid + 1.
The canDistribute function itself is implemented using the same optimized backtracking logic as in the previous approach. The key difference is that the pruning condition is now distribution[i] + cookies[cookieIndex] > mid, and the function returns true as soon as a valid distribution is found, rather than searching for the best one.
class Solution { public int distributeCookies(int[] cookies, int k) { int low = 0, high = 0; for (int c : cookies) { low = Math.max(low, c); high += c; } int ans = high; while (low <= high) { int mid = low + (high - low) / 2; if (canDistribute(cookies, k, mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } private boolean canDistribute(int[] cookies, int k, int maxAllowed) { int[] distribution = new int[k]; // Sorting helps the backtracking check to be more efficient Arrays.sort(cookies); reverse(cookies); return backtrackCheck(0, cookies, distribution, maxAllowed); } private boolean backtrackCheck(int cookieIndex, int[] cookies, int[] distribution, int maxAllowed) { if (cookieIndex == cookies.length) { return true; } for (int i = 0; i < distribution.length; i++) { if (distribution[i] + cookies[cookieIndex] > maxAllowed) { continue; } distribution[i] += cookies[cookieIndex]; if (backtrackCheck(cookieIndex + 1, cookies, distribution, maxAllowed)) { return true; } distribution[i] -= cookies[cookieIndex]; // Backtrack if (distribution[i] == 0) { break; } } return false; } private void reverse(int[] arr) { int i = 0, j = arr.length - 1; while (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } }}Complexity
Time
O(T_backtrack * log(S)), where `S` is the sum of all cookies and `T_backtrack` is the time for the backtracking check. The `log(S)` factor comes from the binary search. While `T_backtrack` is exponential in the worst case, the tight bound `mid` makes it very fast in practice.
Space
O(n + k) for the recursion stack and the `distribution` array used within the `canDistribute` check.
Trade-offs
Pros
Generally the most efficient approach for this class of problems.
The binary search framework provides a very tight bound for the backtracking search, leading to aggressive and effective pruning.
Cons
More complex to implement, as it combines two different algorithmic ideas (binary search and backtracking).
The backtracking check function still has an exponential worst-case time complexity.
Solutions
Solution
class Solution { private int [] cookies ; private int [] cnt ; private int k ; private int n ; private int ans = 1 << 30 ; public int distributeCookies ( int [] cookies , int k ) { n = cookies . length ; cnt = new int [ k ]; // 升序排列 Arrays . sort ( cookies ); this . cookies = cookies ; this . k = k ; // 这里搜索顺序是 n-1, n-2,...0 dfs ( n - 1 ); return ans ; } private void dfs ( int i ) { if ( i < 0 ) { // ans = Arrays.stream(cnt).max().getAsInt(); ans = 0 ; for ( int v : cnt ) { ans = Math . max ( ans , v ); } return ; } for ( int j = 0 ; j < k ; ++ j ) { if ( cnt [ j ] + cookies [ i ] >= ans || ( j > 0 && cnt [ j ] == cnt [ j - 1 ])) { continue ; } cnt [ j ] += cookies [ i ]; dfs ( i - 1 ); cnt [ j ] -= cookies [ i ]; } } }class Solution {public: int distributeCookies(vector<int> &cookies, int k) { sort(cookies.rbegin(), cookies.rend()); int cnt[k]; memset(cnt, 0, sizeof cnt); int n = cookies.size(); int ans = 1 << 30; function<void(int)> dfs = [&](int i) { if (i >= n) { ans = *max_element(cnt, cnt + k); return; } for (int j = 0; j < k; ++j) { if (cnt[j] + cookies[i] >= ans || (j && cnt[j] == cnt[j - 1])) { continue; } cnt[j] += cookies[i]; dfs(i + 1); cnt[j] -= cookies[i]; } }; dfs(0); return ans; }};class Solution: def distributeCookies(self, cookies: List[int], k: int) -> int: def dfs(i): if i >= len(cookies): nonlocal ans ans = max(cnt) return for j in range(k): if cnt[j] + cookies[i] >= ans or (j and cnt[j] == cnt[j - 1]): continue cnt[j] += cookies[i] dfs(i + 1) cnt[j] -= cookies[i] ans = inf cnt = [0] * k cookies . sort(reverse=True) dfs(0) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.