Minimal number of banknotes to pay a bill

Question

Suppose denominations of banknotes follow the infinity Hyperinflation sequence: \$ $1, $2, $5, $10, $20, $50, $100, $200, $500, $1000, $2000, $5000, \cdots \$. How many banknotes are required, at minimum, to pay a \$$n\$ bill?

Consider Alice needs to pay \$ $992 \$ to Bob. It is possible for Alice to use 7 banknotes \$ $500, $200, $200, $50, $20, $20, $2 \$ to pay the bill, but that uses a lot of banknotes. We can see that a better solution is: Alice pays 2 banknotes (\$ $1000, $2 \$), and Bob gives her \$ $10 \$ in change. So, we only need 3 banknotes here.

Formal Definition

Banknotes follow an infinite sequence \$b_i\$: $$ b_n=10\cdot b_{n-3} $$ with base cases $$ b_1=1, b_2=2, b_3=5 $$

When Alice pays \$ $x \$ to Bob, Alice pays \$ a_i \$ banknotes with denominations \$b_i\$. \$ a_i \in \mathbb{Z} \$ And $$ \sum a_ib_i=x $$

\$ a_i \$ may be negative which means Bob gives Alice these banknotes in change.

You are going to calculate: $$ f\left(x\right)=\min_{\sum a_ib_i=x} \sum\left|a_i\right| $$

Input / Output

Input a non-negative number representing the amount of money to pay. Output the minimum number of banknotes required.

Rules

• This is code-golf: Shortest codes in bytes win.
• Your program should be able to handle inputs \$ 0 \le n < 100{,}000 \$ at least. Your algorithm should work for arbitrary large numbers in theory.
• As this questions is only focused on integers, floating point errors are not allowed.

Testcases

Input -> Output
    0 -> 0
    1 -> 1
    2 -> 1
    3 -> 2
    4 -> 2
    5 -> 1
    6 -> 2
    7 -> 2
    8 -> 2
    9 -> 2
   10 -> 1
   11 -> 2
   12 -> 2
   13 -> 3
   14 -> 3
   15 -> 2
   16 -> 3
   17 -> 3
   18 -> 2
   19 -> 2
   20 -> 1
   40 -> 2
   41 -> 3
   42 -> 3
   43 -> 3
   44 -> 3
   45 -> 2
   46 -> 3
   47 -> 3
   48 -> 2
   49 -> 2
   50 -> 1
   90 -> 2
   91 -> 3
   92 -> 3
   93 -> 3
   94 -> 3
   95 -> 2
   96 -> 3
   97 -> 3
   98 -> 2
   99 -> 2
  100 -> 1
  980 -> 2
  981 -> 3
  982 -> 3
  983 -> 4
  984 -> 4
  985 -> 3
  986 -> 4
  987 -> 4
  988 -> 3
  989 -> 3
  990 -> 2
  991 -> 3
  992 -> 3
  993 -> 3
  994 -> 3
  995 -> 2
  996 -> 3
  997 -> 3
  998 -> 2
  999 -> 2
 1000 -> 1
 1341 -> 6
 2531 -> 5
 3301 -> 5
 4624 -> 6
 5207 -> 4
 6389 -> 6
 6628 -> 7
 6933 -> 6
 7625 -> 6
 8899 -> 4
13307 -> 7
23790 -> 5
33160 -> 7
33325 -> 8
40799 -> 5
55641 -> 7
66472 -> 8
77825 -> 6
89869 -> 6
98023 -> 5

Answer 1

Python 2, ^{87 80} 68 bytes

f=lambda x:x>1and min((y%10)**6%305%3+f(y/10*x/y)for y in[x,-x])or x

Try it online!

-7 bytes thanks to @tsh, and -12 bytes thanks to @dingledooper. Thanks to everyone else for their own golf suggestions.

Instead of tearing down the banknotes in the top-down way, this solution builds up the answer from the bottom. Since the number of banknotes needed to pay \$10n\$ is exactly the same as that for \$n\$, we can tear down the banknotes from the one's digit in the following sense:

• If the one's digit is 0, remove the 0 and recurse.

• Otherwise, consider two ways to fulfill the one's digit:

  • Alice pays n%10 to Bob, and then Alice pays whatever banknotes are needed to pay floor(n/10) * 10. Recurse with floor(n/10).
  • Bob pays 10-n%10 to Alice, and then Alice pays whatever banknotes are needed to pay ceil(n/10) * 10. Recurse with ceil(n/10).

  Then we can evaluate the two cases and take their minimum.

In the code, an infinite recursion happens if we don't special-case x=1 as well as x=0, because the ceiling of 1/10 is still 1.

Answer 2

Haskell, 87 bytes

a=0:1:drop 2(zipWith min("0112212222"!a)$"1222212211"!tail a)
s!l=[i+read[j]|i<-l,j<-s]

Try it online!

a is the whole infinite sequence.

This solution combines the fixed point approach of my answer to the previous challenge with Bubbler's excellent observation. Coincidentally, his answer and mine also have the same exact length.

Answer 3

Jelly, 28 21 bytes

DJŻ⁵*×þ⁵ÆḌ¤ạ)F
ÇẠпL’

Takes input as singleton list. Try it online!

–7 per caird coinheringaahing.

Based on ref implementation; lists everything that's 1 away, then 2 away, etc. Adding a Q to the end of the first line makes it go slightly faster.

How?

DJŻ⁵*×þ⁵ÆḌ¤ạ)F  - monadic link; takes integer array
            )   - for each integer
DJ              -   construct [1, ..., number of digits]
  Ż             -   prepend 0
   ⁵*           -   exponent with base 10 (vectorizes)
     ×þ         -   outer product with
       ⁵ÆḌ¤     -   proper divisors of 10; we get banknote 
           ạ    -   absolute difference (vectorizes)
             F  - flatten

ÇẠпL’          - main link; takes integer array
  п            - while
 Ạ              - all integers nonzero,
Ç               - call previous link
    L'          - take length minus 1

Answer 4

JavaScript (ES6),  78  77 bytes

Saved 1 byte thanks to @dingledooper

This is heavily based on Bubbler's answer. Similarly to my answer to a previous challenge, it uses a formula instead of a lookup table.

f=n=>n<2?n:Math.min((g=(n,o)=>(n%10)**6%305%3+f(o/10|0))(n,n),g(10-n%10,n+9))

Try it online!

Answer 5

R, 98 bytes

f=function(a,b=a%%10,c=a%/%10,e=c(0,1,1,2,2,1,2,2:4))`if`(a<2,a,min(e[b+1]+f(c),rev(e)[b]+f(c+1)))

Try it online!

Answer 6

Retina, 102 bytes

^
;$'¶_;
T`d`Rd`.+$
{%0`\d
*
([_;]*)(.*)¶([_;]*)
$1,$3_,$2¶$3,$1_,
+`;_(____|_|)
_;
%O`_*;
)`,.*,

\G_

Try it online! Link includes test cases. Explanation:

^
;$'¶_;
T`d`Rd`.+$

Create a working area with the following values: a) the number of notes used if Alice has not paid Bob enough yet; b) the amount Alice still needs to pay Bob; c) the number of notes used if Alice has overpaid and needs Bob to pay her back; d) the amount Bob still needs to pay back to Alice, minus 1.

{`
)`

Repeat until the full amount has been paid.

%0`\d
*

Convert the next digit of each outstanding amount to unary.

([_;]*)(.*)¶([_;]*)
$1,$3_,$2¶$3,$1_,

Calculate the two ways Alice can under or overpay Bob, depending on whether she under of overpaid Bob last time. If she underpaid last time, she can pay the current digit to remain underpaid, or one more to become overpaid, while if she overpaid last time, Bob can repay the complement to leave Alice overpaid, or one more to make her underpaid again.

+`;_(____|_|)
_;

Calculate the number of additional notes needed to pay each potential digit.

%O`_*;
,.*,

Delete the larger number of notes.

\G_

Convert the number of notes needed for (now exact) payment to decimal.

Answer 7

JavaScript (Node.js), 80 bytes

n=>g=(i=n)=>Math.min(f(i)+f(i+n),i?g(i-1):n);f=n=>n&&(n%10)**29%3571%4+f(n/10|0)

Try it online!

I know there's better answer currently but this is what answer to last question directly lead to