Daily Challenge #45 - Change Machine

Today's challenge is to implement a change function that will accept an integer parameter that represents cents. The function should return the optimal change using the least number of coins.

The function should also return a key for each coin of US currency (specifically 25¢, 10¢, 5¢, and 1¢ coins). The value of each coin should represent the count of each coin in the change. The value for each coin that is not included should return 0.

Ex.
change(31)
{ 25 => 1, 10 => 0, 5 => 1, 1 => 1 }

Good luck!

---

This challenge comes from user Lordnibbler on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge for a future post? Email [e-mail] with your suggestions!

Comments

[Mat-R-Such]

Python

def change(coin,coins = [25,10,5,1]):

    p=0
    ch_tab=[]
    while coin > 0:
        if (coin // coins[p]) > 0:
            ch_tab.append(coin // coins[p])
            coin = coin % coins[p]
            if coin != 0:
                p+=1
        else:
            ch_tab.append(0)
            p+=1
    while len(ch_tab) < 4:
        ch_tab.append(0)
    for i in range(len(coins)):
        print(coins[i], ' ==> ', ch_tab[i])
change(31)

[K.V.Harish]

My solution in js

const change = (amount) => {
  return {
    '25': Math.floor(amount/25),
    '10': Math.floor((a = amount%25)/10),
    '5': Math.floor((b = a%10)/5),
    '1': b % 5
  }
};

[Dev Prakash]

[gist.github.com/devparkk/e5a9ebbe8...]

[Jarod Smith]

Greedy solution in JS

function getChange(n) {
  n = BigInt(n);
  let amount = 0n;
  let coinIndex = 3;
  let change = {
    25: 0n,
    10: 0n,
    5: 0n,
    1: 0n
  }
  const coins = [1n,5n,10n,25n];
  while(amount < n) {
    let divisibilty = ((n - amount) / coins[coinIndex]);
    if (divisibilty >= 1n) {
      change[coins[coinIndex]] += divisibilty;
      amount += (coins[coinIndex] * divisibilty);
    }
    else
      coinIndex--;
  }
  return change;
}

[Matt Ellen-Tsivintzeli]

Another javascript solution:

function change(money)
{
  let coins = [1, 5, 10, 25];
  let parts = new Map([[25, 0],[10,0],[5,0],[1,0]]);
  let currentCoin = coins.pop();
  while(coins.length > 0)
  {
    if(money < currentCoin)
    {
      currentCoin = coins.pop();
    }
    else
    {
      parts.set(currentCoin, parts.get(currentCoin)+1);
      money -= currentCoin;
    }
  }
  return parts;
}

[Jérémie Astor]

Just my two cents, in Gwion

fun void change(int cents) {
  cents / 25 => const int coin25;
  coin25 * 25 -=> cents;
  cents / 10 => const int coin10;
  coin10 *10 -=> cents;
  cents  /5 => const int coin5;
  coin5 * 5 -=> cents;

#! this is a comment
#! below is the debug print.

  <<<
    "{ ",
    "25 => ",   coin25,
    ", 10 => ", coin10,
    ", 5 => ",  coin5,
    ", 1 => ",  cents,
    " }"
  >>>;
}

31 => change;

prints

{ 25 => 1, 10 => 0, 5 => 1, 1 => 1 }

It probably could be written better, but looks like it gets the job done.

[Oleksii Filonenko]

Rust, iterative style:

use std::collections::HashMap;

const COINS: [u32; 4] = [25, 10, 5, 1];

fn change(mut money: u32) -> HashMap<u32, u32> {
    let mut change = HashMap::new();
    for &coin in &COINS {
        change.insert(coin, money / coin);
        money %= coin;
    }
    change
}

[Vivek97]

public static void change(int number)
     {      
        int [] array = {25,10,5,1};
        number = 74;
        for(int m:array)
            {
                System.out.print(m+" =>"+number/m+" ,");
                number = number%m;      
            }
    }

[Alvaro Montoro]

This is a nice solution in Java. But don't forget to remove the number = 74;, otherwise the function will always write the same results.

[Josh]

that guard clause

defmodule CashMachine do                        #🎵 `goto` a CashMachine
  def change(money) do                          #🎵 to get a ticket home
    exchange(money, %{})                        #🎵 the message on the screen
  end                                           #🎵 says "don't make plans, y'all broke"

  defp exchange(0, coins), do: coins            #🎵 no, no, this can't be right
  defp exchange(coin, coins) when coin >= 25 do #🎵 I know that times is tight
    quarters = div(coin, 25)                    #🎵 I've only just been paid
    coin = rem(coin, 25)                        #🎵 three weeks, five days, do that seem
    exchange(coin, put_in(coins[25], quarters)) #🎵 right? no.
  end
  defp exchange(coin, coins) when coin >= 10 do #🎵 I scratch a livin', it ain't easy
    dimes = div(coin, 10)                       #🎵 you know it's a drag
    coin = rem(coin, 10)                        #🎵 I'm always payin', never makin'
    exchange(coin, put_in(coins[10], dimes))    #🎵 but you can't look back
  end                                           
  defp exchange(coin, coins) when coin >= 5 do  #🎵 I wonder if I'll ever get to
    nickels = div(coin, 5)                      #🎵 where I want to be
    coin = rem(coin, 5)                         #🎵 better believe it,
    exchange(coin, put_in(coins[5], nickels))   #🎵 I'm workin' for the CashMachine
  end
  defp exchange(coin, coins) when coin >= 1 do  # lyrics from "Cash Machine"
    exchange(0, put_in(coins[1], coin))         # by Hard-Fi
  end
end

Some people may say "are the comments really necessary?"

I say to them, "Is capitalism?"

[Seiei Miyagi]

ruby <3

def change(amount)
  result = { 25 => 0, 10 => 0, 5 => 0, 1 => 0 }
  case amount
  in 25.. then
    amount -= 25
    result[25] += 1
  in 10.. then
    amount -= 10
    result[10] += 1
  in 5.. then
    amount -= 5
    result[5] += 1
  in 1.. then
    amount -= 1
    result[1] += 1
  end until amount.zero?
  result
end

p change(31)