An algorithm for splitting any amount into 10 yuan, 5 yuan and 2 yuan

Today I went to interview at an e-commerce company, and there was an algorithm question on the written test, as follows:

Input any amount, calculate whether it can be split into 10 yuan, 5 yuan and 2 yuan, and if so how many notes of each.

From the requirement we know we should allocate the highest denomination first, calculate the allocation value from the highest denomination, then take the integer. Then subtract from the input amount the integer calculated from the highest denomination multiplied by the highest denomination, to get the remainder. At first I thought about calculating each separately, nesting multiple layers of if else, but later I found it wasn’t very friendly and got messier and messier. Plus I was handwriting code on A4 paper, which was irritating.

At night when I got home I spent half an hour thinking and wrote this.

function findMoney($money = 0)
{
    $no_text = "不能找回金额为" . $money . "的零钱。";
    $text = "可以找回金额为" . $money . "的零钱,其中";
    if ($money <= 0) {
        echo $no_text;
    }
    $rand = [10, 5, 2];
    for ($i = 0; $i < count($rand); $i++) {
        if ($rand[$i] > 0) {
            $number = floor($money / $rand[$i]);
            $money = $money - $number * $rand[$i];
            $text .= "面额" . $rand[$i] . "元的" . $number . "张" . ",";
            if ($money == 1) {
                echo $no_text . PHP_EOL;
                exit;
            }
        }
    }
    echo $text . PHP_EOL;
}
findMoney(16);

Today is Tuesday; I stayed up fairly late last night and was in a hurry to sleep. In the afternoon I thought about it again and felt something was off.
When the input is 6 or 8 it can’t be allocated.
So I optimized yesterday’s code.

As follows

function findMoney($money = 0)
{
    $no_text = "不能找回金额为" . $money . "的零钱。";
    $text = "可以找回金额为" . $money . "的零钱,其中";
    if ($money <= 0) {
        echo $no_text;
    }
    $rand = [10, 5, 2];
    for ($i = 0; $i < count($rand); $i++) {
        if ($rand[$i] > 0) {
            $number = floor($money / $rand[$i]);
            $money = $money - $number * $rand[$i];
            $text .= "面额" . $rand[$i] . "元的" . $number . "张" . ",";
            if ($money == 1) {
                echo $no_text . PHP_EOL;
                exit;
            }
        }
    }
    echo $text . PHP_EOL;
}
findMoney(16);

Later improvements

As follows

function findMoney($money = 0)
{
    //print_r($money);exit;
    $no_text = "不能找回金额为" . $money . "的零钱。";
    $text = "可以找回金额为" . $money . "的零钱,其中";
    if ($money <= 0) {
        echo $no_text;
    }
    $rand = [10, 5, 2];
    $number = 0;
    for ($i = 0; $i < count($rand); $i++) {
        if (isset($rand[$i])) {
            //the case where it is not evenly divisible
            if (is_float($money / $rand[$i])) {
                $number = $money / $rand[$i];
                if ($money > 0 && $rand[$i] == 5 && ceil($number) != $number) {
                    $text .= "面额" . $rand[$i] . "元的0张" . ",";
                    $text .= getChildMoney($money);
                }else{
                    $number = is_float($number) == 1 ? floor($number) : $number;
                    $money = $money - $number * $rand[$i];
                    $text .= "面额" . $rand[$i] . "元的" . $number . "张" . ",";
                }
            } else {
                $number = $money / $rand[$i];
                $money = $money - $number * $rand[$i];
                $text .= "面额" . $rand[$i] . "元的" . $number . "张" . ",";
                if ($money == 0) {
                    continue;
                }
            }
        }
    }
    if ($money > 0) {
        echo $no_text . PHP_EOL;
    } else {
        echo $text . PHP_EOL;
    }
}

function getChildMoney($money = 0)
{
    $number = $money / 2;
    if (is_float($number)) {
        return false;
    }
    $text = "面额" . $money . "元的" . $number . "张" . ",";
    return $text;
}

findMoney(34);

This way it handles any amount