Watch 10 video solutions for Distribute Money to Maximum Children, a easy level problem involving Math, Greedy. This walkthrough by Aryan Mittal has 1,892 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer money denoting the amount of money (in dollars) that you have and another integer children denoting the number of children that you must distribute the money to.
You have to distribute the money according to the following rules:
1 dollar.4 dollars.Return the maximum number of children who may receive exactly 8 dollars if you distribute the money according to the aforementioned rules. If there is no way to distribute the money, return -1.
Example 1:
Input: money = 20, children = 3 Output: 1 Explanation: The maximum number of children with 8 dollars will be 1. One of the ways to distribute the money is: - 8 dollars to the first child. - 9 dollars to the second child. - 3 dollars to the third child. It can be proven that no distribution exists such that number of children getting 8 dollars is greater than 1.
Example 2:
Input: money = 16, children = 2 Output: 2 Explanation: Each child can be given 8 dollars.
Constraints:
1 <= money <= 2002 <= children <= 30Problem Overview: You are given money dollars and children. Each child must receive at least $1. The goal is to maximize the number of children who receive exactly $8, while ensuring no child ends up with exactly $4. If distributing at least $1 to every child is impossible, return -1.
Approach 1: Brute Force Simulation (O(children) time, O(1) space)
Try every possible number of children that could receive exactly $8. For a candidate value k, compute the required money: 8 * k plus at least 1 dollar for each of the remaining children. Check whether the remaining money creates an invalid case where one child ends up with $4. Iterate from the maximum possible k down to 0 and return the first valid configuration. This approach directly models the constraints and is useful for reasoning about edge cases, but it performs multiple checks across the range of children.
Approach 2: Greedy Distribution (O(1) time, O(1) space)
The optimal solution relies on a greedy observation combined with simple math. First give every child $1. If money < children, the distribution is impossible and the answer is -1. After this base allocation, every child needs an additional $7 to reach $8. Compute how many such upgrades are possible using money / 7, capped by the number of children.
Two edge cases require adjustment. If every child receives $8 but leftover money remains, at least one child would exceed $8, so reduce the count by one. Another special case occurs when exactly one child does not receive $8 and the leftover money equals $3. That child would end up with $4 (1 + 3), which is forbidden. Reduce the count by one to avoid that configuration.
This greedy reasoning works because maximizing $8 allocations always consumes the remaining budget in chunks of $7 after the initial distribution. No additional data structures are required, making it a constant-time calculation driven purely by arithmetic constraints.
Recommended for interviews: The greedy solution is what interviewers expect. It shows you can convert problem constraints into arithmetic reasoning and handle tricky edge cases. Explaining the brute force approach first demonstrates understanding of the constraints, while the greedy optimization highlights problem-solving maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(children) | O(1) | Useful for reasoning about constraints or validating edge cases during initial problem solving |
| Greedy Distribution | O(1) | O(1) | Best approach for interviews and production due to constant-time math-based reasoning |