Scale Engineer

Fair Distribution of Cookies

Med
#2101Time: 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)`).
Patterns
Dynamic ProgrammingBacktrackingBit ManipulationBitmask
Data structures
Array

Prompt

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 <= 8
  • 1 <= cookies[i] <= 105
  • 2 <= 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

    1. Initialize a global variable minUnfairness to a very large value (e.g., Integer.MAX_VALUE).
    1. Create an integer array distribution of size k, initialized to all zeros, to keep track of the cookies assigned to each child.
    1. Define a recursive function backtrack(cookieIndex, distribution).
    1. Base Case: If cookieIndex equals cookies.length, all bags have been distributed. Calculate the maximum value in the distribution array. This is the unfairness for the current distribution. Update minUnfairness = min(minUnfairness, currentUnfairness) and return.
    1. Recursive Step: For the cookie bag at cookieIndex, iterate through each child i from 0 to k-1.
    1. In the loop, add cookies[cookieIndex] to distribution[i] to assign the bag to child i.
    1. Make a recursive call for the next cookie bag: backtrack(cookieIndex + 1, distribution).
    1. After the recursive call returns, subtract cookies[cookieIndex] from distribution[i]. This is the "backtracking" step, which undoes the choice to explore other possibilities.
    1. To start the process, call backtrack(0, new int[k]) from the main function.
    1. After the initial call completes, minUnfairness will hold the minimum possible unfairness.

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.

Solutions

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 ]; } } }

Video 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.

← Previous

Previous problem

Next →

Next problem