Make denomination program using PHP

I have encountered below scenario:

Input amount: 3897

Output:

[
    1000 => 3,
    500 => 1,
    200 => 1,
    100 => 1,
    50 => 1,
    20 => 2,
    10 => 0,
    5 => 1,
    1 => 2
]

Description : Here I want to find out the length of a series numbers in a given input value (how many time a series number can be come in a given input number)

Lets Break down the example to understand what I want :

3897 = (1000*3)+ (500*1)+(200*1)+(100*1)+(50*1)+(20*2)+(10*0)+(5*1)+(1*2)

So I need to find out the length of these number series(1000,500,200,100,….) in a given input.

I tried below solution and it worked fine, but I am sure a better solution will be there for-sure.

<?php


$input = 3897;

function denominationProgram($input){
    $data = $input;
    $array = [1000 =>0,500=>0,200=>0,100=>0,50=>0,20=>0,10=>0,5=>0,1=>0];
    while($data > 0){
        if($data > 1000){
            $array[1000] = intdiv($data, 1000);
            $data -= 1000*$array[1000];
        }
        
        if($data < 1000 && $data > 500){
            $array[500] = intdiv($data, 500);
            $data -= 500*$array[500];
        }
         
        if($data < 500 && $data > 200){
            $array[200] = intdiv($data, 200);
            $data -= 200*$array[200];
        }
        
        if($data < 200 && $data > 100){
            $array[100] = intdiv($data, 100);
            $data -= 100*$array[100];
        }
        
        if($data < 100 && $data > 50){
            $array[50] = intdiv($data, 50);
            $data -= 50*$array[50];
        }
        
        if($data < 50 && $data > 20){
            $array[20] = intdiv($data, 20);
            $data -= 20*$array[20];
        }
        
        if($data < 20 && $data > 10){
            $array[10] = intdiv($data, 10);
            $data -= 10*$array[10];
        }
        
        if($data < 10 && $data > 5){
            $array[5] = intdiv($data, 5);
            $data -= 5*$array[5];
        }
        
        if($data < 5 && $data > 1){
            $array[1] = intdiv($data, 1);
            $data -= 1*$array[1]; 
        }
    }
    
    print_r($array);
    
}

denominationProgram($input);

A question regarding same is asked, but it’s deleted now, so I am not sure that you guys are able to see it or not?

Answer

<?php


$input = 3897;

function denominationProgram($amount){
    $array = [1000 => 0, 500 => 0, 200 => 0, 100 => 0, 50 => 0, 20 => 0, 10 => 0, 5 => 0, 1 => 0];
    krsort($array);// if given array isn't sorted in descending order
    foreach($array as $coin_type => $quantity){
        $quantity = intval($amount / $coin_type);
        $amount -= $coin_type * $quantity;
        $array[$coin_type] = $quantity;
    }
    
    if($amount > 0){
        throw new Exception("Denomination not possible.");
    }
    
    return $array;
}

print_r(denominationProgram($input));

First step is to ksort the denominations array. This is necessary because we would want to knock off larger portion of the amount with big coin types and then go for the smaller ones(like using 3 1000 type coins instead of 60 50 type coins for an amount of 3000). This also gives us the minimum coins to be used to satisfy the amount and give it to an end user.

Second, is to loop over the denominations array and capture the max number of coins we can use for a given coin type for the amount at hand.

Later on , just subtract the coin type amount from the actual amount and pass it to the next denominations in queue.

At the end, return the result. Throw an exception if in case the denominations are not sufficient to sum up to the amount. In this context, exception is of no use since we have 1 coin type with infinite supply. But, I added it since it’s a good practice otherwise.