Distribute Money to Maximum Children

Difficulty: Easy | Acceptance: 20.60% | Paid: No Topics: Math, Greedy

You are given an integer money representing the amount of money (in dollars) and an integer children representing the number of children that you need to distribute the money to.

You need to distribute the money according to the following rules:

1. Every child must receive at least 1 dollar.
2. Every child must receive an integer amount of money.
3. If a child receives exactly 8 dollars, it is considered a “maximum” amount.
4. No child should receive exactly 4 dollars.

Return the maximum number of children who can receive a “maximum” amount of 8 dollars. If it is impossible to distribute the money following the rules, return -1.

• Examples
• Constraints
• Mathematical Greedy
• Brute Force / Iterative Check

Examples

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

Mathematical Greedy

Intuition First, ensure every child gets at least 1 dollar. Then, try to give 7 more dollars (to make 8) to as many children as possible. If the remaining money after this distribution leaves a remainder that forces a child to have 4 dollars, we adjust by taking 7 dollars back from one child who already has 8.

Steps

• If money is less than children, return -1 (not enough money for everyone to get 1).
• Calculate remaining money after giving 1 dollar to each child: remaining = money - children.
• Calculate the maximum number of children that can get 8 dollars: count = remaining // 7.
• Calculate the remainder: rem = remaining % 7.
• If the remainder is 3:
  • If count is 0, it means we have exactly 3 extra dollars to give to one child (making it 4), which is invalid. Return -1.
  • Otherwise, we must reduce count by 1. We take 7 dollars from one child (who now has 1) and add it to the 3 remainder, giving 10 to the last child (1 + 10 = 11), which is valid.
• Return count.

class Solution:
    def distMoney(self, money: int, children: int) -> int:
        if money < children:
            return -1
        remaining = money - children
        count = remaining // 7
        rem = remaining % 7
        if rem == 3:
            if count == 0:
                return -1
            count -= 1
        return count

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This is the optimal solution as it uses constant arithmetic operations.

Brute Force / Iterative Check

Intuition Try to give 8 dollars to the maximum possible number of children, then check if the remaining money can be distributed to the remaining children without violating the rules. If not, reduce the number of children getting 8 dollars and try again.

Steps

• Iterate k from min(children, money // 8) down to 0.
• For each k, calculate the remaining money rem_money = money - 8 * k and remaining children rem_children = children - k.
• Check if the distribution is valid:
  • rem_money must be at least rem_children (everyone gets at least 1).
  • If there is only 1 remaining child (rem_children == 1), ensure they don’t get exactly 4 dollars (rem_money != 4).
• If valid, return k.
• If the loop finishes without finding a valid k, return -1.

class Solution:
    def distMoney(self, money: int, children: int) -> int:
        max_k = min(children, money // 8)
        for k in range(max_k, -1, -1):
            rem_money = money - 8 * k
            rem_children = children - k
            if rem_money < rem_children:
                continue
            if rem_children == 1 and rem_money == 4:
                continue
            return k
        return -1

Complexity

• Time: O(N) where N is the number of children or money (up to 10⁹ in worst case).
• Space: O(1)
• Notes: This approach is conceptually simple but inefficient for large inputs compared to the mathematical solution.