LeetCode Solutions Blog

Fair Distribution of Cookies

Number: 1418

Difficulty: Medium

Paid? No

Problem Description

Given an array where each element represents the number of cookies in a bag, and an integer k representing the number of children, assign every bag to one child so that the unfairness (defined as the maximum total cookies any child receives) is minimized. Each bag must go entirely to a single child and cannot be split.

Key Insights

Use a backtracking approach to try every possible distribution since the number of cookie bags (n) is small (n ≤ 8).
Maintain an array representing the total cookies each child has received.
Prune paths early if the current maximum exceeds the current best solution.
The goal is to minimize the maximum sum among children across all distributions.

Space and Time Complexity

Time Complexity: O(k^n) in the worst case, since we assign n bags to k children. Space Complexity: O(n) due to recursion depth and auxiliary data structures.

Solution

We can solve the problem using a recursive backtracking algorithm. At each recursive call, we consider giving the current cookie bag to each child and update their totals accordingly. After processing all bags, we compute the unfairness (maximum among all children's totals) and update the global minimum if the current distribution is better. The small input size allows an exponential approach. Key structures include an array (or vector) to store each child's accumulated cookies and a recursion mechanism to explore all assignments.

Code Solutions

# Python solution using recursion and backtracking.
def distributeCookies(cookies, k):
    # Initialize the minimum unfairness as a large number.
    min_unfairness = float('inf')
    # Initialize a list to store the running sum of cookies for each child.
    children = [0] * k

    def backtrack(index):
        nonlocal min_unfairness
        # Base case: if we've assigned all bags.
        if index == len(cookies):
            # Update the minimum unfairness with the current maximum value among children.
            min_unfairness = min(min_unfairness, max(children))
            return

        # Try giving the current cookie bag to each child.
        for i in range(k):
            children[i] += cookies[index]
            # Pruning: only proceed if the current child's sum does not exceed known min_unfairness.
            if max(children) < min_unfairness:
                backtrack(index + 1)
            children[i] -= cookies[index]
            # Optimization: if this child hasn't been given a cookie bag yet,
            # break to avoid redundant permutations.
            if children[i] == 0:
                break

    backtrack(0)
    return min_unfairness

# Example usage:
print(distributeCookies([8,15,10,20,8], 2))  # Output: 31
print(distributeCookies([6,1,3,2,2,4,1,2], 3))  # Output: 7