Number of coins needed to make change

Question

Relatable scenario: I'm going to the store to buy a single item, but only have a $100k bill. As a result, I need exactly $99,979 in change, and in the fewest coins/bills possible because I'm quite obviously a very practical person.

The denominations of these coins/bills follow the hyperinflation sequence: \$1, 2, 5, 10, 20, 50, 100, 200\$, and so on.

(I'd proposed an OEIS sequence for this, but the first 100k terms are identical to another one so it got rejected)

Task:

Given an amount of money as a nonnegative integer, such as \$73\$, return the minimum number of coins/bills needed to total to that amount. In this example, it would be \$4\$. The coins required would be \$50 + 20 + 2 + 1\$.

As per the standard rules for sequence, you can also choose to return all terms up to an inputted index, or return a (potentially infinite) lazy list or generator that represents the whole sequence.

Test cases:

0       0
1       1
2       1
3       2
4       2
5       1
6       2
7       2
8       3
9       3
10      1
11      2
20      1
30      2
37      4
90      3
111     3
147     5
1000    1
1002    2
1010    2
12478   9

Other:

This is code-golf, so shortest answer in bytes per language wins!

Answer 1

Husk, 11 9 8 bytes

Edit: -1 byte thanks to caird coinheringaahing

ṁo⌈½ṁB5d

Try it online!

       d   # get the digits
    ṁB5    # convert them all to base-5
           # (this gives a 1 for each 5-denomination coin needed,
           # as well as the leftover for each digit.
           # We'll need 2 more coins for those with leftover 3 or 4, 
           # and only one more coin if the leftover is 1 or 2.)
ṁo         # So: map across all the base-5 digits
   ½       # dividing each of them by 2
  ⌈        # and then getting the ceiling;
           # and finally output the sum

Answer 2

JavaScript (ES7),  36  35 bytes

Similar to other answers. Using a Black Magic formula instead of a lookup table.

f=n=>n&&(n%10)**29%3571%4+f(n/10|0)

Try it online!

Here is a script that looks for \$(p,m)\$ pairs such that \$(n^p\bmod m)\bmod 4=a_n\$ for all \$n\in[0..9]\$.

It's worth noting that this code takes IEEE-754 precision errors into account. So the results are correct but the math is wrong.

With exact values, we could do instead:

$$\big((n \bmod 10)^{18}\bmod 4011\big)\bmod 4$$

Or better yet, as suggested by @dingledooper:

$$\big((n \bmod 10)^{55}\bmod 767\big)\bmod 4$$

For instance, in Python:

Python 2, 40 bytes

f=lambda n:n and(n%10)**55%767%4+f(n/10)

Try it online!

---

JavaScript (ES7), 71 bytes

Expects the amount as a string.

A naive recursive approach that subtracts one coin/bill at a time.

n=>(k=10**n.length,g=t=>+n?k>n?g(t,k/=~++i%3?2:2.5):g(t+1,n-=k):t)(i=0)

Try it online!

Answer 3

Haskell, ^55…41 40 bytes

• -1 byte thanks to xnor, for using a string instead of the hard-coded list.

a=0:tail[i+read[j]|i<-a,j<-"0112212233"]

Try it online!

a is the infinite sequence.

How?

It's not hard to find the recursive formula $$ a(n)=a\left(\left\lfloor\frac{n}{10}\right\rfloor\right)+a(n \operatorname{mod} 10) $$ with the base cases for \$n\in\{0,\ldots,9\}\$ given by $$ [0,1,1,2,2,1,2,2,3,3]. $$

This means that the infinite list a satisfies the equality

a==[i+j|i<-a,j<-[0,1,1,2,2,1,2,2,3,3]]

Now, Haskell is magical, but not magical enough to compute a from the definition

a=[i+j|i<-a,j<-[0,1,1,2,2,1,2,2,3,3]]

However, giving the first term explicitly is enough:

a=0:tail[i+j|i<-a,j<-[0,1,1,2,2,1,2,2,3,3]]

The 40-bytes code above is equivalent to this, but shorter.

Answer 4

R, 54 51 47 45 bytes

Edit: converted to console input instead of a full function to try not to fall behind Robin Ryder's answer

d=utf8ToInt(scan(,''))-48;sum(d>0,d>5,d%%5>2)

Try it online!

Answer 5

R, 64 52 50 45 bytes

sum(c(1,2,1:3)[.6*utf8ToInt(scan(,""))-28.4])

Try it online!

Same strategy as Delfad0r's Haskell answer, which is nicely explained.

First, scan(,"") reads in input as a string. Then, utf8ToInt(...)-48 takes a string of digits and converts it to a vector of integer digits. This works out shorter than taking input as an integer and splitting it into digits.

The digits from 0 to 9 then have to be mapped to the vector c(0,1,1,2,2,1,2,2,3,3). To do this, consider the vector a=c(1,2,1,2,3). For digit d, a[.4+d*.6] is the value we want. This uses the fact that when calling a non-integer index in a vector (say a[2.8]), R rounds down the index (here a[2]), and also the fact that a[0] returns NULL which will be ignored in the sum.

Putting this operation with the operation to convert the string to digits simplifies to .6*utf8ToInt(...)-28.4.

Note that Dominic van Essen has a solution of (currently) the same length with a different strategy.

Answer 6

Jelly, 7 bytes

Db5FHĊS

Try it online!

Steals Ports Dominic Van Essen's Husk answer, be sure to upvote that!

How it works

Db5FHĊS - Main link. Takes an integer n on the left
D       - Convert to digits
 b5     - Convert each digit to base 5
   F    - Flatten
    H   - Halve each
     Ċ  - Ceiling of each
      S - SUm

---

Jelly, 11 bytes

Dị“FȮŀO’D¤S

Try it online!

How it works

Dị“FȮŀO’D¤S - Main link. Takes n on the left
D           - Convert n to digits
         ¤  - Create a nilad:
  “FȮŀO’    -   Compressed integer: 1122122330
        D   -   To digits
 ị          - Index into the digits of this integer
          S - Sum

Answer 7

05AB1E, 11 bytes

S<•δ¬Èº•sèO

Try it online!

Same approach as my Jelly answer.

How it works

S<•δ¬Èº•sèO - Program. Input: n
S           - Cast n to digits
 <          - Decrement
  •δ¬Èº•    - Compressed integer: 1122122330
        sè  - Using n's digits, index into the digits of 1122122330
          O - Sum

Kudos to Kevin Cruijssen's excellent integer compressor!

Answer 8

Husk, 23 bytes

L◄Lfo=⁰Σ↑o≤⁰LṖƒ(+İ€m*10

Try it online!

Extremely slow past 11.

Explanation

L◄Lfo=⁰Σ↑o≤⁰LṖƒ(+İ€m*10
              ƒ(        create an infinite list using:
                 ݀     currency denomination builtin: [1,1/2,1/5,...200]
                +       plus
                   m*10 the input mapped to *10
                        this gives [1,1/2,...100] + 10*([1,1/2,...100] + (10*[1,1/2,...100]...))
             Ṗ          powerset(unordered)
        ↑o≤⁰L           take all sequences which have length ≤ input
                        this makes sure everything till [1]*n is in the list
   fo=⁰Σ                filter out the ones which do not sum to the input
 ◄L                     maximum element by length
L                       take the length

Answer 9

Wolfram Language (Mathematica), 39 bytes

⌈.4#⌉-⌊#/5⌋&@*IntegerDigits/*Tr

Try it online!

Answer 10

Python 2, 37 bytes

f=lambda n:n and n/5%2-n%5/-2+f(n/10)

Try it online!

Uses a formula rather than a lookup table for each digit. n/5%2 counts the five-cent coin, and subtracting -n%5/-2 is equivalent to adding (n%5+1)/2 for the one- and two-cent coins.

n%10      0 1 2 3 4 5 6 7 8 9
-----------------------------
n/5%2     0 0 0 0 0 1 1 1 1 1
0-n%5/-2  0 1 1 2 2 0 1 1 2 2
Total     0 1 1 2 2 1 2 2 3 3

Answer 11

C (gcc), 39 bytes

f(n){n=n?f(n/10)+"


"[n%10]:0;}

Try it online!

JavaScript (Node.js), 37 bytes

f=n=>n&&+"0112212233"[n%10]+f(n/10|0)

Try it online!

Answer 12

Python 2, 48 bytes

f=lambda x:x and int("0112212233"[x%10])+f(x/10)

Try it online!

49 bytes in Python 3 because you'd need // for floor division.

Answer 13

Charcoal, 13 bytes

ＩΣ⭆Ｓ⭆↨Ｉι⁵Ｌ↨λ³

Try it online! Link is to verbose version of code. Explanation:

   Ｓ            Convert input to a string
  ⭆             Map over characters and join
       ι        Current character
      Ｉ         Cast to integer
     ↨  ⁵       Convert to base 5
    ⭆           Map over base 5 digits and join
           λ    Current digit
          ↨ ³   Convert to base 3
         Ｌ      Take the length
 Σ              Take the (digital) sum
Ｉ               Cast to string
                Implicitly print

Table of base 5 digit to base 3 length:

Decimal Base 3 Length
0       []     0
1       [1]    1
2       [2]    1
3       [1, 0] 2
4       [1, 1] 2

Answer 14

Vyxal, d, 5 bytes

5vτ½⌈

Try it Online!

A port of the Jelly answer which is a port of short husk answer.

Explained

5vτ½⌈
5vτ   # convert each digit of the input to base 5
   ½  # halve each item in that list (halving vectorises all the way down)
    ⌈ # ceiling each item in that list
      # -d deep sums the list and implicitly outputs

Answer 15

Retina 0.8.2, 20 15 bytes

.
$*1,
1{5}|11?

Try it online! Link includes test cases. Explanation:

.
$*1,

Convert each digit to unary separately.

1{5}|11?

Count the number of 5s, 2s and 1s needed to make each digit.

Answer 16

05AB1E (legacy), 7 bytes

5δв˜;îO

Port of @Dominic van Essen's Husk answer, so make sure to upvote him as well!

Uses the legacy version of 05AB1E to get rid of a leading S that would be required in the new version of 05AB1E in this case, due to the way the δ acts on strings/integers.

Try it online or verify all test cases.

Explanation:

 δ       # Map each digit in the (implicit) input-integer to:
5 в      #  A base-5 list
   ˜     # Flatten this list of lists
    ;    # Halve each integer
     î   # Ceil each float
      O  # Sum the integers in the list together
         # (after which the result is output implicitly)