Fair Distribution of Cookies solution and explanation
9 more videos on this problem
Fair Distribution of Cookies | Khandani Backtracking Template | Leetcode-2305 | Explanation | CodingcodestorywithMIK · 15:31 · 18K views
LeetCode 2305 Fair Distribution of CookiesJeevan Kumar - Cracckify · 9:36 · 6K views
Fair Distribution of Cookies - Leetcode 2305 - PythonTechError · 7:15 · 5K views
Weekly Contest 297| Leetcode 2303 2304 2305 |Minimum Path Cost in a Grid| Fair Distribution CookiesCoding Decoded · 19:12 · 2K views
Weekly Contest 297 | 2305. Fair Distribution of CookiescodingMohan · 9:57 · 2K views
2305. Fair Distribution of Cookies (Leetcode Medium)Programming Live with Larry · 16:47 · 1K views
Fair Distribution of Cookies | LeetCode 2305 | Backtracking | Choice Diagram | Weekly ContestBottomUp · 17:47 · 1K views
Fair Distribution of Cookies - LeetCode 2305 - PythonAlpha-Code · 12:52 · 1K views
Fair Distribution of Cookies | LeetCode 2305 | JavaThe TryIt Project · 14:49 · 958 views
2305 || Fair Distribution of Cookies || C++ || Leetcode Daily ChallengeCodeFreaks · 15:24 · 860 views
The problem
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
Approach overview
Problem Overview: You are given an array where each element represents a bag of cookies and an integer k representing children. Each bag must go to exactly one child. The goal is to minimize unfairness, defined as the maximum number of cookies received by any child.
Approach 1: Backtracking with Pruning (Time: O(k^n), Space: O(n))
This approach tries every possible way to distribute cookie bags among k children using backtracking. Maintain an array where dist[i] tracks the total cookies assigned to the i-th child. For each bag, iterate through children and assign the bag recursively. After assigning all bags, compute the maximum value in dist and track the minimum possible unfairness.
Pruning significantly reduces the search space. If the current distribution already exceeds the best unfairness found so far, stop exploring that branch. Another common optimization skips assigning a bag to multiple children with the same current cookie count to avoid duplicate states. This approach is practical because the constraint on the number of bags is small.
Approach 2: Dynamic Programming with Bitmasking (Time: O(k * 3^n), Space: O(k * 2^n))
This approach models the problem using dynamic programming combined with bitmasking. Each bitmask represents a subset of cookie bags. First precompute the total cookies for every subset mask using bit operations. Then define dp[i][mask] as the minimum unfairness when distributing the bags represented by mask among i children.
For each state, iterate through all submasks of mask. Treat the submask as the set of bags assigned to the current child and combine it with the optimal distribution of the remaining bags. The unfairness becomes max(dp[i-1][mask ^ submask], subsetSum[submask]). Minimizing this value across all submasks gives the optimal distribution.
This method systematically explores subsets rather than permutations, making it easier to reason about overlapping subproblems. It performs well when the number of bags is small (typically ≤ 8), which keeps the bitmask state space manageable.
Recommended for interviews: The backtracking solution is usually expected. It demonstrates recursion, pruning, and state management. Interviewers want to see how you reduce exponential search with pruning. The bitmask dynamic programming approach is more advanced and shows deeper understanding of subset DP, which can stand out in system-level or algorithm-heavy interviews.
Approach 1: Backtracking Approach
This approach leverages backtracking to explore all possible ways of distributing the bags of cookies among the children. We utilize a recursive function to attempt to give each bag of cookies to any of the available children. At each step, we update the total cookies received by the child to whom the current bag is assigned. The goal is to minimize the maximum number of cookies any child receives, known as unfairness.
from itertools import permutations
class Solution:
def distributeCookies(self, cookies, k):
def distribute(index):
nonlocal min_unfairness
if index == len(cookies):
min_unfairness = min(min_unfairness, max(distribution))
return
for i in range(k):
distribution[i] += cookies[index]
distribute(index + 1)
distribution[i] -= cookies[index]
distribution = [0] * k
min_unfairness = float('inf')
distribute(0)
return min_unfairnessimport java.util.Arrays;
class Solution {
private void distribute(int[] cookies, int[] distribution, int index, int[] minUnfairness) {
if (index == cookies.length) {
int maxCookies = Arrays.stream(distribution).max().getAsInt();
if (maxCookies < minUnfairness[0]) {
minUnfairness[0] = maxCookies;
}
return;
}
for (int i = 0; i < distribution.length; i++) {
distribution[i] += cookies[index];
distribute(cookies, distribution, index + 1, minUnfairness);
distribution[i] -= cookies[index];
}
}
public int distributeCookies(int[] cookies, int k) {
int[] distribution = new int[k];
int[] minUnfairness = new int[]{Integer.MAX_VALUE};
distribute(cookies, distribution, 0, minUnfairness);
return minUnfairness[0];
}
}#include <vector>
#include <algorithm>
#include <climits>
void distribute(std::vector<int>& cookies, std::vector<int>& distribution, int index, int& minUnfairness) {
if (index == cookies.size()) {
minUnfairness = std::min(minUnfairness, *std::max_element(distribution.begin(), distribution.end()));
return;
}
for (int& d : distribution) {
d += cookies[index];
distribute(cookies, distribution, index + 1, minUnfairness);
d -= cookies[index];
}
}
int distributeCookies(std::vector<int>& cookies, int k) {
std::vector<int> distribution(k, 0);
int minUnfairness = INT_MAX;
distribute(cookies, distribution, 0, minUnfairness);
return minUnfairness;
}function distributeCookies(cookies, k) {
let minUnfairness = Infinity;
let distribution = new Array(k).fill(0);
function distribute(index) {
if (index === cookies.length) {
minUnfairness = Math.min(minUnfairness, Math.max(...distribution));
return;
}
for (let i = 0; i < k; i++) {
distribution[i] += cookies[index];
distribute(index + 1);
distribution[i] -= cookies[index];
}
}
distribute(0);
return minUnfairness;
}#include <limits.h>
void distribute(int *cookies, int cookiesSize, int k, int *distribution, int index, int *minUnfairness) {
if (index == cookiesSize) {
int maxCookies = INT_MIN;
for (int i = 0; i < k; i++) {
if (distribution[i] > maxCookies) {
maxCookies = distribution[i];
}
}
if (maxCookies < *minUnfairness) {
*minUnfairness = maxCookies;
}
return;
}
for (int i = 0; i < k; i++) {
distribution[i] += cookies[index];
distribute(cookies, cookiesSize, k, distribution, index + 1, minUnfairness);
distribution[i] -= cookies[index];
}
}
int distributeCookies(int* cookies, int cookiesSize, int k) {
int distribution[k];
for (int i = 0; i < k; i++) {
distribution[i] = 0;
}
int minUnfairness = INT_MAX;
distribute(cookies, cookiesSize, k, distribution, 0, &minUnfairness);
return minUnfairness;
}using System;
public class Solution {
public int DistributeCookies(int[] cookies, int k) {
int[] distribution = new int[k];
int minUnfairness = int.MaxValue;
Distribute(cookies, distribution, 0, ref minUnfairness);
return minUnfairness;
}
private void Distribute(int[] cookies, int[] distribution, int index, ref int minUnfairness) {
if (index == cookies.Length) {
int currentMax = Int32.MinValue;
foreach (int d in distribution) {
currentMax = Math.Max(currentMax, d);
}
minUnfairness = Math.Min(minUnfairness, currentMax);
return;
}
for (int i = 0; i < distribution.Length; i++) {
distribution[i] += cookies[index];
Distribute(cookies, distribution, index + 1, ref minUnfairness);
distribution[i] -= cookies[index];
}
}
}The Python solution uses recursion and backtracking with a helper function to explore cookie distribution. Inbuilt dividers are leveraged to handle each recursive step systematically. The algorithm seeks to minimize the worst distribution outcome through compute comparisons across recursive completions.
Time Complexity: O(k^n), due to recursive exploration of all paths.
Space Complexity: O(k + n), for recursive depth and storing distributions.
Approach 2: Dynamic Programming via Bitmasking
This approach uses bitmasking in conjunction with dynamic programming to keep track of all combinations of cookie distributions among k children. We aim to optimize processing by encoding choices using bitmasks to represent different subsets of cookies. This method alleviates computational overhead by avoiding permutation/combination evaluation via iterative states and sub-state record tracking. We leverage a DP technique where dp[mask][children] represents the minimum unfairness achievable assigning the selected cookie combination (mask) across given children.
import sys
def distributeCookies(cookies, k):
cookiesSize = len(cookies)
maxMask = 1 << cookiesSize
dp = [[sys.maxsize] * k for _ in range(maxMask)]
dp[0][0] = 0
for mask in range(maxMask):
for children in range(k):
if dp[mask][children] == sys.maxsize:
continue
for next in range(cookiesSize):
cookieCost = sum(cookies[bit] for bit in range(cookiesSize) if mask & (1 << bit))
newMask = mask
for bit in range(next, cookiesSize):
if not (mask & (1 << bit)):
cookieCost += cookies[bit]
newMask |= (1 << bit)
dp[newMask][children] = min(dp[newMask][children], max(cookieCost, dp[mask][children]))
return dp[maxMask - 1][k - 1]import java.util.Arrays;
class Solution {
public int distributeCookies(int[] cookies, int k) {
int cookiesSize = cookies.length;
int maxMask = 1 << cookiesSize;
int[][] dp = new int[maxMask][k];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
dp[0][0] = 0;
for (int mask = 0; mask < maxMask; ++mask) {
for (int children = 0; children < k; ++children) {
if (dp[mask][children] == Integer.MAX_VALUE) continue;
for (int next = 0; next < cookiesSize; ++next) {
int cookieCost = 0;
for (int bit = 0; bit < cookiesSize; ++bit) {
if ((mask & (1 << bit)) != 0) cookieCost += cookies[bit];
}
int newMask = mask;
for (int bit = next; bit < cookiesSize; ++bit) {
if ((mask & (1 << bit)) == 0) {
cookieCost += cookies[bit];
newMask |= (1 << bit);
dp[newMask][children] = Math.min(dp[newMask][children], Math.max(cookieCost, dp[mask][children]));
}
}
}
}
}
return dp[maxMask - 1][k - 1];
}
}#include <vector>
#include <algorithm>
#include <climits>
int distributeCookies(std::vector<int>& cookies, int k) {
int cookiesSize = cookies.size();
int maxMask = 1 << cookiesSize;
std::vector<std::vector<int>> dp(maxMask, std::vector<int>(k, INT_MAX));
dp[0][0] = 0;
for (int mask = 0; mask < maxMask; ++mask) {
for (int children = 0; children < k; ++children) {
if (dp[mask][children] == INT_MAX) continue;
for (int next = 0; next < cookiesSize; ++next) {
int cookieCost = 0;
for (int bit = 0; bit < cookiesSize; ++bit) {
if (mask & (1 << bit)) cookieCost += cookies[bit];
}
int newMask = mask;
for (int bit = next; bit < cookiesSize; ++bit) {
if (!(mask & (1 << bit))) {
cookieCost += cookies[bit];
newMask |= (1 << bit);
dp[newMask][children] = std::min(dp[newMask][children], std::max(cookieCost, dp[mask][children]));
}
}
}
}
}
return dp[maxMask - 1][k - 1];
}function distributeCookies(cookies, k) {
const cookiesSize = cookies.length;
const maxMask = 1 << cookiesSize;
const dp = Array.from({ length: maxMask }, () => Array(k).fill(Infinity));
dp[0][0] = 0;
for (let mask = 0; mask < maxMask; mask++) {
for (let children = 0; children < k; children++) {
if (dp[mask][children] === Infinity) continue;
for (let next = 0; next < cookiesSize; next++) {
let cookieCost = 0;
for (let bit = 0; bit < cookiesSize; bit++) {
if (mask & (1 << bit)) cookieCost += cookies[bit];
}
let newMask = mask;
for (let bit = next; bit < cookiesSize; bit++) {
if (!(mask & (1 << bit))) {
cookieCost += cookies[bit];
newMask |= (1 << bit);
dp[newMask][children] = Math.min(dp[newMask][children], Math.max(cookieCost, dp[mask][children]));
}
}
}
}
}
return dp[maxMask - 1][k - 1];
}#include <limits.h>
#include <stdbool.h>
#include <math.h>
int distributeCookies(int* cookies, int cookiesSize, int k) {
int maxMask = 1 << cookiesSize;
int dp[maxMask][k];
for (int mask = 0; mask < maxMask; ++mask) {
for (int i = 0; i < k; ++i) {
dp[mask][i] = INT_MAX;
}
}
dp[0][0] = 0;
for (int mask = 0; mask < maxMask; ++mask) {
for (int children = 0; children < k; ++children) {
if (dp[mask][children] == INT_MAX) {
continue;
}
for (int next = 0; next < cookiesSize; ++next) {
int cookieCost = 0;
for (int bit = 0; bit < cookiesSize; ++bit) {
if (mask & (1 << bit)) {
cookieCost += cookies[bit];
}
}
int newMask = mask;
for (int bit = next; bit < cookiesSize; ++bit) {
if (!(mask & (1 << bit))) {
cookieCost += cookies[bit];
newMask |= (1 << bit);
dp[newMask][children] = fmin(dp[newMask][children], fmax(cookieCost, dp[mask][children]));
}
}
}
}
}
return dp[(1 << cookiesSize) - 1][k - 1];
}using System;
public class Solution {
public int DistributeCookies(int[] cookies, int k) {
int cookiesSize = cookies.Length;
int maxMask = 1 << cookiesSize;
int[][] dp = new int[maxMask][];
for (int i = 0; i < maxMask; i++) {
dp[i] = new int[k];
Array.Fill(dp[i], int.MaxValue);
}
dp[0][0] = 0;
for (int mask = 0; mask < maxMask; mask++) {
for (int childNum = 0; childNum < k; childNum++) {
if (dp[mask][childNum] == int.MaxValue) continue;
int cookieCost = 0;
for (int bit = 0; bit < cookiesSize; bit++) {
if ((mask & (1 << bit)) != 0) {
cookieCost += cookies[bit];
}
}
for (int next = 0; next < cookiesSize; next++) {
int newMask = mask;
int updatedCost = cookieCost;
for (int bit = next; bit < cookiesSize; bit++) {
if ((mask & (1 << bit)) == 0) {
updatedCost += cookies[bit];
newMask |= (1 << bit);
dp[newMask][childNum] = Math.Min(dp[newMask][childNum], Math.Max(updatedCost, dp[mask][childNum]));
}
}
}
}
}
return dp[maxMask - 1][k - 1];
}
}Utilizing Python’s computational proficiency, the solution employs a dynamic programming framework with bitmasking methodologies. This method entails armed subsets capable of tracking present distributions down to respective resources, allocating these across a root data figure. Consequential DPs facilitate computations along possible distributions, maintaining constant storage alignment on key objective modulations.
Time Complexity: O(n * 2^n * k). Synoptic mindfulness evaluation across active bitmask space shifts with cookies hindrance calculated expeditiously.
Space Complexity: O(2^n * k), space is saved using pre-mapped divisions, underwriting the adaptive resolution upkeep.
Approach 3: Backtracking + Pruning
First, we sort the array cookies in descending order (to reduce the number of searches), and then create an array cnt of length k to store the number of cookies each child gets. Also, we use a variable ans to maintain the current minimum degree of unfairness, initialized to a very large value.
Next, we start from the first snack pack. For the current snack pack i, we enumerate each child j. If the cookies cookies[i] in the current snack pack are given to child j, making the degree of unfairness greater than or equal to ans, or the number of cookies the current child already has is the same as the previous child, then we don't need to consider giving the cookies in the current snack pack to child j, just skip it (pruning). Otherwise, we give the cookies cookies[i] in the current snack pack to child j, and then continue to consider the next snack pack. When we have considered all the snack packs, we update the value of ans, then backtrack to the previous snack pack, and continue to enumerate which child to give the cookies in the current snack pack to.
Finally, we return ans.
function distributeCookies(cookies: number[], k: number): number {
const cnt = new Array(k).fill(0);
let ans = 1 << 30;
const dfs = (i: number) => {
if (i >= cookies.length) {
ans = Math.max(...cnt);
return;
}
for (let 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;
}func distributeCookies(cookies []int, k int) int {
sort.Sort(sort.Reverse(sort.IntSlice(cookies)))
cnt := make([]int, k)
ans := 1 << 30
var dfs func(int)
dfs = func(i int) {
if i >= len(cookies) {
ans = slices.Max(cnt)
return
}
for 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]
}
}
dfs(0)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(k^n), due to recursive exploration of all paths. |
| Dynamic Programming via Bitmasking | Time Complexity: O(n * 2^n * k). Synoptic mindfulness evaluation across active bitmask space shifts with cookies hindrance calculated expeditiously. |
| Backtracking + Pruning | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(k^n) | O(n) | Best practical solution when number of cookie bags is small. Easy to implement and preferred in interviews. |
| Dynamic Programming with Bitmask | O(k * 3^n) | O(k * 2^n) | Useful when practicing subset DP or when you want a structured state-based solution. |
Frequently asked questions
Is Fair Distribution of Cookies easy or hard?
The problem is rated Medium on LeetCode. The core idea of trying all distributions is straightforward, but writing efficient pruning logic and recognizing the bitmask DP alternative requires solid experience with backtracking and subset dynamic programming.
Fair Distribution of Cookies Python/Java solution
Both Python and Java implementations typically use recursive backtracking with pruning. Maintain an array of size k to store cookies assigned to each child and recursively place each bag. The optimal result is the minimum possible value of the maximum cookies assigned to any child.
How to solve Fair Distribution of Cookies in O(n)?
An O(n) solution is not possible because the problem requires exploring different assignments of bags to children. The search space grows exponentially with the number of bags. The most efficient practical solutions are backtracking with pruning or dynamic programming using bitmasks.
What is the best approach for Fair Distribution of Cookies?
Backtracking with pruning is the most practical approach. It recursively assigns each cookie bag to one of the k children while tracking the current cookie totals. Pruning branches where the current unfairness already exceeds the best result drastically reduces the search space. Time complexity is roughly O(k^n) but works well because the number of bags is small.
Is Fair Distribution of Cookies asked at Google/Amazon/Meta?
Backtracking and subset DP problems similar to this frequently appear in interviews at companies like Google, Amazon, and Meta. The exact problem may not always appear, but the pattern of minimizing a maximum value using recursion and pruning is common.
What data structure is used in Fair Distribution of Cookies?
The main structures include arrays to track cookie totals per child, recursion stacks for backtracking, and bitmasks to represent subsets in the dynamic programming solution. Bit manipulation helps encode subsets efficiently for DP state transitions.
What is the time complexity of Fair Distribution of Cookies?
The backtracking solution runs in O(k^n) time where n is the number of cookie bags and k is the number of children. With pruning, many branches are skipped in practice. The dynamic programming bitmask approach runs in about O(k * 3^n) due to iterating over all masks and their submasks.