Distribute Money to Maximum Children — Problem & Solution
Distribute Money to Maximum Children solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Distribute Money to Maximum Children is an easy coding problem on math and greedy, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Math, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have money dollars to distribute among children children under these rules:
- Every child must receive at least 1 dollar.
- No child may receive exactly 4 dollars.
- All the money must be handed out.
Return the maximum number of children who can receive exactly 8 dollars, or -1 if the distribution is impossible.
Example 1
Input: money = 20, children = 3
Output: 1
Explanation: 8 + 9 + 3, or 8 + 3 + 9 — only one child can get exactly 8.
Example 2
Input: money = 16, children = 2
Output: 2
Explanation: 8 + 8.
Example 3
Input: money = 2, children = 3
Output: -1
Explanation: There is not even one dollar per child.
Constraints
1 <= money <= 2002 <= children <= 30
Hints for Distribute Money to Maximum Children
Hint 1
Give every child 1 dollar first; that leaves
money - childrento top up with.Hint 2
Each 8-dollar child needs 7 more dollars, so at most
(money - children) / 7of them.Hint 3
Two edge cases spoil the count: leftover money with every child already at 8, and a final child stuck on exactly 4.
How to solve Distribute Money to Maximum Children
Hand out the mandatory 1 dollar each, then upgrade children to 8 by spending 7 more on each. Only two corner cases prevent the naive count from being achievable.
Approach
- Return
-1whenmoney < children— the minimum cannot be met. - Set
rem = money - childrenandeights = min(rem / 7, children), then subtracteights * 7fromrem. - If every child got 8 but money remains, one child must take the excess — decrement
eights. - If exactly one child is left over and they would hold
1 + 3 = 4dollars, that is forbidden — decrementeights. - Return
eights.
Why it works
Greedy is optimal because upgrading a child to 8 costs a fixed 7 regardless of who it is. The two adjustments are the only ways a full-looking count is unachievable: leftover cash has nowhere legal to go, and the forbidden value 4 arises only from a single remaining child holding 1 + 3.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Forgetting the
rem == 3with one child remaining case gives an off-by-one on inputs likemoney = 17, children = 2. - Forgetting that leftover money must go somewhere over-reports when
moneyfar exceeds8 * children. money == childrenis valid — everyone gets 1 dollar and the answer is 0.
Reference solution
Python
def distMoney(money: int, children: int) -> int:
if money < children:
return -1
rem = money - children
eights = min(rem // 7, children)
rem -= eights * 7
if eights == children and rem > 0:
eights -= 1
elif eights == children - 1 and rem == 3:
eights -= 1
return eightsJava
public static int distMoney(int money, int children) {
if (money < children) return -1;
int rem = money - children;
int eights = Math.min(rem / 7, children);
rem -= eights * 7;
if (eights == children && rem > 0) eights--;
else if (eights == children - 1 && rem == 3) eights--;
return eights;
}C++
int distMoney(int money, int children) {
if (money < children) return -1;
int rem = money - children;
int eights = min(rem / 7, children);
rem -= eights * 7;
if (eights == children && rem > 0) eights--;
else if (eights == children - 1 && rem == 3) eights--;
return eights;
}JavaScript
var distMoney = function(money, children) {
if (money < children) return -1;
let rem = money - children;
let eights = Math.floor(rem / 7);
if (eights > children) eights = children;
rem -= eights * 7;
if (eights === children && rem > 0) eights--;
else if (eights === children - 1 && rem === 3) eights--;
return eights;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Greedy Algorithms