Distribute Money to Maximum Children

Easy
565.

Distribute Money to Maximum Children

Distribute Money to Maximum Children is an easy coding problem on math and greedy, asked in Amazon and Google interviews.

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 <= 200
  • 2 <= children <= 30
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} money
 * @param {number} children
 * @return {number}
 */
var distMoney = function(money, children) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 200
  • 2 <= children <= 30

Hints for Distribute Money to Maximum Children

  1. Hint 1

    Give every child 1 dollar first; that leaves money - children to top up with.

  2. Hint 2

    Each 8-dollar child needs 7 more dollars, so at most (money - children) / 7 of them.

  3. 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

  1. Return -1 when money < children — the minimum cannot be met.
  2. Set rem = money - children and eights = min(rem / 7, children), then subtract eights * 7 from rem.
  3. If every child got 8 but money remains, one child must take the excess — decrement eights.
  4. If exactly one child is left over and they would hold 1 + 3 = 4 dollars, that is forbidden — decrement eights.
  5. 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 == 3 with one child remaining case gives an off-by-one on inputs like money = 17, children = 2.
  • Forgetting that leftover money must go somewhere over-reports when money far exceeds 8 * children.
  • money == children is 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 eights

Java

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