Fair Distribution of Cookies
Medium · Backtracking · Array · Backtracking · Bit Manipulation · Dynamic Programming
Problem
You are given an array cookies, where cookies[i] is the number of cookies in the i-th bag, and an integer k, the number of children. Every bag must be handed, whole, to exactly one child; bags cannot be split.
The unfairness of a distribution is the largest number of cookies any single child receives. Return the minimum unfairness over all possible distributions.
Examples
Input: cookies = [5,8,3,4], k = 2 Output: 11
Giving {8,3} to one child and {5,4} to the other yields totals 11 and 9.
Input: cookies = [6,1,1,1,1], k = 3 Output: 6
The bag of 6 alone forces an unfairness of at least 6, and {6}, {1,1}, {1,1} achieves it.
Input: cookies = [8,15,10,20,8], k = 2 Output: 31
{20, 10} and {15, 8, 8}: totals 30 and 31.
Constraints
- 2 <= cookies.length <= 8
- 1 <= cookies[i] <= 10^5
- 2 <= k <= cookies.length
Approaches
- Baseline: every assignment — time O(k^n · n), space O(n + k)
Follow-up
The unfairness only scores a finished distribution; the search itself is the same for other scores. The use cases make the smallest share as large as possible, and decide whether a given cap can be met.
Related problems
Start free on Cariara · Coding problems · System design studio
