We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Distribute Money to Maximum Children

Number: 2663

Difficulty: Easy

Paid? No

Companies: Amazon, Zendesk

Problem Description

You are given a total amount of money and a number of children. You must distribute all the money so that every child gets at least 1 dollar and no child receives exactly 4 dollars. Under these constraints, determine the maximum number of children who can receive exactly 8 dollars. If it is impossible to distribute the money following the rules, return -1.

Key Insights

  • Start by ensuring that every child gets the mandatory minimum: 1 dollar.
  • After the initial distribution, the extra money available is (money - children).
  • To get a child to exactly 8 dollars, they need an extra 7 dollars (since 1 + 7 = 8).
  • Maximally, without any restrictions, the number of children that can receive 8 dollars would be (money - children) // 7.
  • However, an edge case occurs when the remaining extra money left for non-8 recipients is exactly 3 (causing one child to end up with 1+3 = 4 dollars), which is forbidden. In that case, one fewer child should be given 8 dollars.

Space and Time Complexity

Time Complexity: O(1) – The solution performs a constant number of operations. Space Complexity: O(1) – Only a few extra variables are used.

Solution

The idea is to give every child 1 dollar first so that we meet the minimum requirement. The remaining money is then used to try to raise as many children as possible to exactly 8 dollars (i.e. give them an extra 7 dollars each). We calculate the candidate number as extra // 7 (where extra = money - children). However, if this distribution causes one of the remaining children to receive exactly 4 dollars (i.e. when leftover extra money after giving the 7 dollars is exactly 3), we reduce the count by 1 to avoid the forbidden amount. Finally, if the initial conditions cannot be met (money smaller than children), return -1.

Code Solutions

# Python solution
def max_children_with_exactly_eight(money: int, children: int) -> int:
    # Check if it is possible to distribute at least 1 dollar per child
    if money < children:
        return -1

    # Calculate the extra money after giving each child 1 dollar
    extra = money - children

    # Calculate maximum potential children that can be given an extra 7 dollars (to reach 8 dollars)
    max_eights = extra // 7

    # Do not assign more than the total number of children
    max_eights = min(max_eights, children)

    # Check for the edge case: if the leftover extra money causes a child to get exactly 4 dollars.
    # This happens if extra - (max_eights * 7) equals exactly 3.
    if max_eights > 0 and (extra - max_eights * 7) == 3:
        max_eights -= 1

    return max_eights

# Example usage:
print(max_children_with_exactly_eight(20, 3))  # Output: 1
print(max_children_with_exactly_eight(16, 2))  # Output: 2
← Back to All Questions