# Number of coins needed to make change

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 , 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 , so shortest answer in bytes per language wins!

• @RobinRyder Yes, sorry about that Apr 12 at 14:28
• Very closely related, if not practically a duplicate: Minimally Making Change Apr 12 at 14:31
• @Etheryte The premise is similar, but the challenge is very different. I doubt the solutions to the two will be anywhere near similar. Apr 12 at 14:33
• Can I take input as a list of digits? Apr 12 at 15:05
• The store manager is going to get suspicious... Apr 13 at 10:15

# Husk, 119 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

• 8 bytes, using ceiling and halve rather than increment and integer divide Apr 12 at 17:59
• @cairdcoinheringaahing - Nice! Thankyou very much! Apr 13 at 9:17

# 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!

• In Python, I think (n%10)**55%767%4 is 1 byte shorter. Apr 12 at 18:13
• @dingledooper Weird. This was within my search bounds but I guess I simply didn't notice it. Thank you! Apr 12 at 18:29
• "How can you find the black magic (n%10)**55%767%4 that is equivalent to the [0123456789] -> [0112212233] lookup table?" - asked by jolreal, who doesn't have enough reputation to comment Apr 13 at 12:11
• I used n/5%2-n%5/-2 in my Python answer, can that be profitably adapted to JS?
– xnor
Apr 13 at 21:05
• @xnor Unfortunately, I don't think it's as interesting in JS that it is in Python. By using BigInts to force integer division, the best I can think of so far is 35 bytes as well. Apr 13 at 21:49

# 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.

• Nice recursive list! Looks like compressing the hardcoded list to a string breaks ahead: TIO
– xnor
Apr 12 at 19:28

# R, 545147 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!

• Well done! I'm not giving up yet… Apr 12 at 17:28
• It's a tie! Apr 13 at 18:44

# 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


# R, 645250 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.

• <s>Bah!</s> Nice work! Apr 12 at 15:41
• Your solutions are getting more and more esoteric! Apr 14 at 6:40
• This is a very, very clever solution! Well done! Much better than mine (even if the bytes are the same). I'm very jealous... and (despite trying for too long last night) I don't think I'll be able to bet mine any shorter... Apr 14 at 10:48

# 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

• A port of the Husk answer is also shorter in 05AB1E: S5δв˜;îO. And can be another byte shorter in the legacy version of 05AB1E by removing the leading S. May 4 at 13:09
• @KevinCruijssen You're welcome to post that if you'd like, I'm going to keep this as the digit lookup approach May 4 at 13:11
• It's basically the same as your top Jelly answer, but sure, I'll post it as a separated answer. May 4 at 13:12

# 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

• "currency denomination builtin"? Seriously? :P Apr 12 at 15:11
• yep, "Euro coin and bill values" :P Apr 12 at 15:16
• This would seem to be the perfect challenge for the 'currency denomination builtin', and yet... Apr 12 at 15:26
• @DominicvanEssen I figured there was a much better method, looking at all the non golflang answers. (I just couldn't pass up using fix) Apr 12 at 15:28

# Wolfram Language (Mathematica), 39 bytes

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


Try it online!

# 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


# 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!

• Golfed your JS one: f=n=>n&&+"311221223"[n%9]+f(n/10|0) Apr 12 at 15:02
• @RedwolfPrograms How does that work?
– l4m2
Apr 12 at 15:04
• Oh wait, it doesn't. Sorry about that (forgot n%10 can be 0 with n being nonzero) Apr 12 at 15:04

# 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.

# 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


# 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


# 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.

# 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.

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)