We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Fair Distribution of Cookies

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each child can receive whole bags of cookies, and the distribution must ensure all bags are allocated.
  • The goal is to minimize the maximum number of cookies any child receives.
  • A backtracking approach can be used to explore all possible distributions of cookies among children while keeping track of the maximum cookies received by any child.
  • Given the constraints (2 <= cookies.length <= 8), a brute-force or backtracking solution is feasible.

Space and Time Complexity

Time Complexity: O(k^n), where n is the number of cookie bags and k is the number of children. This is because we explore all distributions recursively.
Space Complexity: O(k), to store the current distribution of cookies to each child.

Solution

The solution employs a backtracking approach. The idea is to recursively assign each bag of cookies to one of the k children while tracking the total cookies assigned to each child. After each assignment, we check if the maximum cookies any child has received exceeds the current minimum unfairness. If it does, we backtrack and try a different assignment. This process continues until we find the optimal distribution with the least unfairness.

Code Solutions

def distributeCookies(cookies, k):
    def backtrack(index, distribution):
        if index == len(cookies):
            return max(distribution)
        
        min_unfairness = float('inf')
        for i in range(k):
            distribution[i] += cookies[index]
            min_unfairness = min(min_unfairness, backtrack(index + 1, distribution))
            distribution[i] -= cookies[index]
        return min_unfairness

    return backtrack(0, [0] * k)

# 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
← Back to All Questions