Fairest Snack Handout
MediumBacktracking
Problem
You have bags of snacks, bags[i] being the number of snacks in bag i, and k children. Every bag must go, unopened, to exactly one child.
The unfairness of a handout is the largest number of snacks any single child receives. Return the minimum possible unfairness.
Example 1
- Input:
- bags = [8, 15, 10, 20, 8], k = 2
- Output:
- 31
[8, 15, 8] → 31 and [10, 20] → 30. No split does better than 31.
Example 2
- Input:
- bags = [6, 1, 3, 2, 2, 4, 1, 2], k = 3
- Output:
- 7
[6, 1], [3, 2, 2], [4, 1, 2].
Constraints
- 1 ≤ k ≤ bags.length ≤ 8
- 1 ≤ bags[i] ≤ 10^5
Hint
Show the first hint
With at most 8 bags you can afford to try assignments, but prune them.
Walkthrough
How to approach it
01Clarify before coding
- Can a child receive nothing? Yes, if k is large, but then someone else carries more.
- Can bags be opened? No, each bag goes whole to one child.
- Sizes? Up to 8 bags and 8 children, so k^n ≤ 16.7 million raw assignments.
02Brute force
Try all k^n assignments of bags to children and take the minimum of the maximum load.
Cost: O(n · k^n): 16.7 million assignments in the worst case, each with an O(n) evaluation.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.