LeetCode Ts-2591. Distribute Money to Maximum Children

    AllenLi
    CodingLeetCode JS-GreedyLeetCode Js-Math

    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.

    你給與一個整數 money 表示你擁有的金額（以美元為單位），以及一個整數 children 表示你需要將錢分配給多少個孩子。
你必須按照以下規則分配這筆錢：
- 所有錢都必須分配出去。
- 每個人至少要拿到 1 美元。
- 沒有人能得到 4 美元。
按照上述規則分配後，回傳最多有多少個孩子能剛好得到 8 美元。
如果沒有辦法分配，則傳回 -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.

    Solution:
    如果錢少於小孩數量，則回傳 -1，因為不夠分配給每個小孩 1 塊，
    如果錢多於小孩數量，則分配給每個小孩各 1 塊(題目要求)。
    上述分配之後，
    假設每個小孩都拿 8 塊(每人先拿 1 塊，並在領取 7 塊，總共 8 塊)，
    則答案就是小孩的數量(最多獲得 8 塊的人數)，
    反之則依序進行分配，
    第一個小孩領滿 8 元之後，
    需要判斷錢是否不夠(變負的)，
    或是最後一個小孩領到 3 塊(原本的 1 塊 + 3 塊 = 4 塊)，
    則此分配不符合需跳出回圈，不列入計算。

    Code 1: BigO(n)

    function distMoney(money: number, children: number): number {
    let ans: number = 0;
    if (money < children) return -1;
    money -= children;
    if (children * 7 === money) return children;
    for (let i = 1; i < children; i++) {
        money -= 7;
        if (money < 0 || (money === 3 && i === children - 1)) break;
        ans = i;
    }
    return ans;
};

    FlowChart:
    Example 1

    Input: money = 20, children = 3

money: 20, children: 3
after giving 1 to each child, money left: 17
after giving 7 to child 1, money left: 10
current ans: 1
after giving 7 to child 2, money left: 3
final ans: 1

    Example 2

    Input: money = 16, children = 2

money: 16, children: 2
after giving 1 to each child, money left: 14
16 - 2 = 14, children * 7 = 14
return children; // 2

    Related Posts