# Distribute Money to Maximum Children
**Difficulty:** EASY
[External](https://leetcode.com/problems/distribute-money-to-maximum-children)
Canonical: https://scaleengineer.com/dsa/problems/distribute-money-to-maximum-children
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [Zendesk](https://scaleengineer.com/companies/zendesk)
---
## Problem
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:

* All money must be distributed.
* Everyone must receive at least `1` dollar.
* Nobody receives `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 <= 200`
* `2 <= children <= 30`

# Approaches
## Iterative Search
This approach systematically checks every possible number of children that can receive $8, starting from the highest possible number (`children`) down to zero. For each potential count, it verifies if the remaining money can be distributed to the remaining children while adhering to all the given rules. The first count that allows for a valid distribution is guaranteed to be the maximum, so we can return it immediately. This method is essentially a linear search for the answer.
**Time:** O(children) because, in the worst case, the loop runs from `children` down to 0. · **Space:** O(1) as it only uses a few variables for calculations, regardless of the input size.
**Pros:** The logic is straightforward and easy to follow.; It correctly handles all edge cases by its nature of checking every possibility.
**Cons:** Slightly less efficient than a direct mathematical solution.; For very large constraints on `children`, this approach could be too slow, but it's perfectly fine for the given constraints.
### Explanation
The core idea is to iterate and check. We want to maximize the number of children, `k`, who get $8. We can simply try all possible values for `k` and see which ones are valid.

To be efficient, we should start our search from the highest possible value of `k`, which is `children`, and go down to `0`. The first value of `k` that allows a valid distribution of the entire `money` will be our answer.

For a given `k`, we check its validity as follows:
1.  Calculate the money given to these `k` children: `spent = k * 8`. If `spent > money`, this `k` is impossible.
2.  Calculate the remaining money `rem_money = money - spent` and remaining children `rem_children = children - k`.
3.  Now, we must distribute `rem_money` among `rem_children`.
    *   If `rem_children == 0`, all children were given $8. This is only valid if `rem_money == 0`.
    *   If `rem_children > 0`, every one of them must get at least $1, so `rem_money >= rem_children`. Additionally, we must not be forced to give a child exactly $4. This problematic scenario only occurs when there is exactly one child left (`rem_children == 1`) and the exact amount of money left is $4 (`rem_money == 4`).

If a value of `k` passes these checks, it's a valid solution. Since we are iterating downwards, the first one we find is the maximum.

```java
class Solution {
    public int distMoney(int money, int children) {
        if (money < children) {
            return -1;
        }
        // Iterate from the maximum possible children getting $8 downwards.
        for (int k = children; k >= 0; k--) {
            int spent_money = k * 8;
            if (spent_money > money) {
                continue;
            }
            int rem_money = money - spent_money;
            int rem_children = children - k;

            if (rem_children == 0) {
                if (rem_money == 0) {
                    return k; // Perfect distribution
                }
            } else {
                // Check if remaining money can be distributed
                if (rem_money >= rem_children) {
                    // Check for the forbidden $4 case
                    if (rem_children == 1 && rem_money == 4) {
                        continue; // This k is invalid
                    }
                    return k; // Found a valid distribution
                }
            }
        }
        return -1; // Should not be reached if money >= children
    }
}
```
### Algorithm
1. If `money < children`, it's impossible to give each child at least $1. Return -1.
2. Iterate through the number of children who could receive $8, let's call it `k`, from the maximum possible (`children`) down to `0`.
3. For each `k`, calculate the money that would be spent (`k * 8`) and the remaining money (`rem_money`) and remaining children (`rem_children`).
4. If the money spent exceeds the total `money`, this `k` is not feasible, so we continue to `k-1`.
5. Check if the `rem_money` can be validly distributed among `rem_children`:
    - If `rem_children` is 0, `rem_money` must also be 0. If so, we found a valid distribution for `k` children, and since we iterate downwards, this is the maximum. Return `k`.
    - If `rem_children` is greater than 0, we must ensure two conditions: (a) each remaining child can get at least $1 (`rem_money >= rem_children`), and (b) we don't run into the special case where we are forced to give the last child $4 (this happens only when `rem_children == 1` and `rem_money == 4`).
6. If both conditions in step 5 are met, `k` is a valid answer. Return `k`.
7. If the loop completes, it implies no solution was found, which should only happen if the initial check `money < children` was true. A fallback return of -1 handles this.

## Constant Time Mathematical Approach
A more optimal solution can be achieved by using mathematical reasoning to directly calculate the result in constant time. This approach avoids any iteration by breaking the problem down into a set of distinct cases based on the relationship between the amount of money and the number of children. By analyzing the constraints, we can derive a formula to find the answer.
**Time:** O(1) because it involves a fixed number of arithmetic operations and comparisons. · **Space:** O(1) as no extra space proportional to the input size is required.
**Pros:** Extremely efficient, with a constant time complexity.; It's the optimal solution in terms of performance.
**Cons:** The logic is more complex and requires careful mathematical case analysis to derive.; It can be less intuitive to come up with during an interview compared to the iterative approach.
### Explanation
This approach solves the problem without any loops by performing a case analysis.

First, we handle the trivial invalid case: if `money < children`, it's impossible, so we return -1.

To simplify the problem, we can first satisfy the rule that everyone gets at least $1. We distribute $1 to each of the `children`, which uses up `children` dollars. The remaining money is `money - children`. Now, our goal is to distribute this remaining money to give as many children as possible an additional $7 to make their total $8.

The number of children we can give an additional $7 to is `count = (money - children) / 7`. The money left after this is `remainder = (money - children) % 7`.

We can now determine the final answer with a few checks:

1.  **Too much money (`count > children`):** This happens if `money` was initially much larger than `8 * children`. We can't give everyone $8 because money would be left over. The best we can do is give `children - 1` kids $8 and the last kid all the rest. The answer is `children - 1`.

2.  **Just enough money (`count == children`):** We have enough to give everyone an additional $7. If `remainder == 0`, everyone gets exactly $8. The answer is `children`. If `remainder > 0`, the extra money must go to one child, meaning only `children - 1` children end up with exactly $8.

3.  **Not enough money (`count < children`):** We can give `count` children $8. The `remainder` must be distributed among the `children - count` kids who still have only $1. The only problem arises if there's exactly one child left (`children - count == 1`) and the `remainder` is exactly 3, as this child would receive a total of `$1 + $3 = $4`. In this specific scenario, we must break up one of the $8 packages, reducing the number of children with $8 by one. So the answer is `count - 1`. In all other sub-cases, `count` is the correct answer.

```java
class Solution {
    public int distMoney(int money, int children) {
        // 1. Not enough money to give every child $1.
        if (money < children) {
            return -1;
        }

        // 2. Special case: too much money. We can't give everyone $8.
        // The max is children - 1. The last child gets the large remainder.
        if (money > 8 * children) {
            return children - 1;
        }

        // 3. Special case: giving k = children - 1 leaves the last child with $4.
        // This happens when money = 8 * (children - 1) + 4, which is 8 * children - 4.
        // In this case, the answer must be k = children - 2.
        if (money == 8 * children - 4) {
            return children - 2;
        }

        // 4. General case: The number of children getting $8 is limited by the need
        // to give the rest at least $1. money - 8k >= children - k => k <= (money - children) / 7.
        return (money - children) / 7;
    }
}
```
### Algorithm
1. Handle the base case: if `money < children`, return -1.
2. Conceptually, give every child $1 first to satisfy a core rule. The remaining money is `money - children`.
3. The problem now is to distribute this remaining amount to the `children`, where each needs an additional $7 to reach a total of $8.
4. Calculate the maximum number of children who can receive an additional $7: `count = (money - children) / 7`.
5. Calculate the leftover money after this distribution: `remainder = (money - children) % 7`.
6. Analyze the results based on a few distinct cases:
    - If `count` is greater than `children`, it means we have more than enough money to give everyone $8. We can't give everyone $8 because money would be left over. The answer is `children - 1`.
    - If `count` equals `children`, we can give everyone $8 if and only if the `remainder` is 0. If there is a remainder, one child must take it, so only `children - 1` children get exactly $8.
    - If `count` is less than `children`, `count` is our candidate answer. However, we must check the `$4` rule. This rule is violated if we are left with one child (`children - count == 1`) who has $1, and the `remainder` to be given is $3 (totaling $4). In this specific scenario, the answer is `count - 1`. Otherwise, the answer is `count`.

# Solutions
### Java

```java
class Solution {
public
  int distMoney(int money, int children) {
    if (money < children) {
      return -1;
    }
    if (money > 8 * children) {
      return children - 1;
    }
    if (money == 8 * children - 4) {
      return children - 2;
    }
```

### CPP

```cpp
class Solution {
public:
  int distMoney(int money, int children) {
    if (money < children) {
      return -1;
    }
    if (money > 8 * children) {
      return children - 1;
    }
    if (money == 8 * children - 4) {
      return children - 2;
    }
```

### Python

```python
class Solution:
    # money-8x >= children-x, x <= (money-children)/7 return ( money - children ) // 7
    def distMoney(self, money: int, children: int) -> int: if money < children: return - 1 if money > 8 * children: return children - 1 if money == 8 * children - 4: return children - 2

```