Find the largest banknote

Question

Banknotes in many countries come in denominations of 1,2,5,10,20,50,100,200,500,1000, etc. That is, one of \$ \{ 1,2,5\} \$ times a power of \$10\$. This is OEIS A051109, except we'll extend the sequence to bigger values.

Given a positive integer as the input, the program should output the largest bank note that is less than or equal to the input. The input will be less than \$2^{63}\$.

Examples:

1 => 1
2 => 2
3 => 2
5 => 5
9 => 5
42 => 20
49 => 20
50 => 50
99 => 50
100 => 100
729871 => 500000
3789345345234 => 2000000000000
999999999999999999 => 500000000000000000

Answer 1

Python 2, 39 bytes

f=lambda n:n>9and 10*f(n/10)or 5>>5/-~n

Try it online!

Answer 2

Perl 5 -p, 24 20 19 bytes

Credit to @DomHastings for shortening this entry.

s/\B./0/g;y;3-9;225

Try it online!

Answer 3

Python 2, 38 bytes

lambda a,*b:`5>>5/-~int(a)`+"0"*len(b)

Try it online!

A function that takes in the number as characters, and returns a numeric string.

Use xnor's formula to get from a digit to 1, 2, or 5.

Answer 4

Raku, 30 bytes

{first /^(1|2|5)0*$/,($_...1)}

Try it online!

Counts down from the input, finding the first number that is a 1,2 or a 5 followed by only zeroes

Answer 5

J, 26 bytes

(>:{:@#])1 2 5*<.&.(10&^.)

Try it online!

How it works

(>:{:@#])1 2 5*<.&.(10&^.)                             250
                   (10&^.) logarithm to base 10          3.x
               <.&.        and floor                     3
                   (10&^.) and reverse the logarithm:  100
         1 2 5*            1 2 5 times that:   100 200 500
(>:     )                  input greater-equal list? 1 1 0
      #]                   take from list:         100 200
   {:@                     last element                200

Answer 6

R, 51 47 bytes

Golfed down 4 bytes by Giuseppe.

function(x,z=c(5,2,1)*10^nchar(x)/10)z[z<=x][1]

Try it online!

Answer 7

Rockstar, 187 bytes

Listen to B
cast B at 0 into C
D is 5
E is 2
F is 1
let G be F
if C is as strong as E
let G be E

if C is as strong as D
let G be D

while B is as strong as 10
let B be B over 10
let G be G of 10

say G

Ungolfed and a bit more Rockstarish (yes this is valid syntax)

sunset was spellbound
god was a roundabout

Listen to the devil
cast the devil at sunset into the storm

(The kids are young don't let em grow up too fast)
Tommy is 5
Jimmy is 2
Alice is 1

(My kids are my heroes)
let my Hero be Alice

if the storm is as strong as Jimmy
let my Hero be Jimmy

if the storm is as strong as Tommy
let my Hero be Tommy

while the devil is as strong as god
let the devil be the devil over god
let my hero be my hero of god

say my hero

First time ever using this language, just having a bit of fun

Answer 8

Charcoal, 12 bytes

⭆Ｓ∧¬κ÷⁵⊕÷⁵⊕ι

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

 Ｓ             Convert input to a string
⭆              Map over digits and join
    κ           Current index
   ¬            Is zero
  ∧             Boolean AND
           ι    Current digit
          ⊕     Incremented
         ⁵      Literal 5
        ÷       Integer divide
       ⊕        Incremented
      ⁵         Literal 5
     ÷          Integer divide
                Implicitly print

Answer 9

Husk, 6 5 bytes

Ω£İ₅←

Try it online!

Explanation

It's basically a built-in.

Ω£İ₅←   Implicit input.
    ←   Decrement
Ω       until
 £      is an element of
  İ₅    Infinite list of powers of 10 and multiples by 2 or 5:
            [1,2,5,10,20,50,100,200,500,..]

Here's a more interesting 10-byte solution that avoids İ₅:

Ωö€Ḋ10d↔d←

Try it online! Explained:

Ωö€Ḋ10d↔d←   Implicit input.
         ←   Decrement
Ω            until
 ö           composition of 4 functions:
        d     number to digits,
       ↔      reverse,
      d       back to number,
  €           is an element of
   Ḋ          list of divisors of
    10        10 (so 1, 2, 5 or 10, and the last one is impossible).

Answer 10

JavaScript, 34 bytes

f=n=>n<2?1:n<5?2:n<10?5:10*f(n/10)

Try it online!

A recursive function that checks each denomination, otherwise divides by 10 and tries again.

Note that the last test case fails because it exceeds the maximum safe integer.

-6 bytes don't need to check <1

Answer 11

APL (Dyalog Unicode), 17 bytes

10⊥≢↑'125'(⍎⍸⊃⊣)⊃

Try it online!

A tacit function that takes input as a string, and returns an integer. ⎕FR←1287 is needed to get exact results for high numbers.

How it works

10⊥≢↑'125'(⍎⍸⊃⊣)⊃  ⍝ Input: a string of digits without leading zeros
                ⊃  ⍝ First char
     '125'( ⍸  )   ⍝ Interval index into '125'; 1→1; 2-4→2; 5-9→3
             ⊃⊣    ⍝ The char at the above index of '125'
           ⍎       ⍝ Eval it, so it becomes numeric
   ≢↑              ⍝ Pad with zeros to the length of the input
10⊥                ⍝ Convert from base 10 digits to integer

Answer 12

Japt, 12 10 bytes

I/O as an integer.

@AvXìw}aaU

Try it

---

Alternative (w/ -m flag), 10 bytes

I/O as a string or an array of digits. Credit, again, to xnor for the formula to find the first digit.

V?T:5Á5/°U

Try it

---

Original (with -h flag), 12 bytes

I/O as integer strings.

#}ì úTUl)f§U

Try it

#}ì úTUl)f§U     :Implicit input of integer string U
#}               :125
  ì              :To digit array
    ú            :Right pad each
     T           :  With 0
      Ul         :  To the length of U
        )        :End padding
         f       :Filter
          §U     :  Less than or equal to U
                 :Implicit output of last element

Answer 13

Pyth, 26 bytes 21 bytes

efgQTm*d^Ttl+Qk[1 2 5

Try it online!

 

Old Solution:

V60 aY*h^%N3 2^T/N3;efgQTY

Explanation:
Using ((n % 3) ** 2 + 1) * 10**int(n/3) To calculate a the banknote for n in the series.

V60 aY*h^%N3 2^T/N3;efgQTY
V60                         Looping 60 times.
      *h^%N3 2^T/N3         Calculate the current iterations banknote value
    aY                      Append it to list Y
                     fgQTY  Filter the list for all values less than or equal to input
                    e       Grab the last value in the list.

Try it online!

Answer 14

Husk, 14 bytes

:ḟ≤←¹s521mK'0t

Try it online!

This is my first Husk answer.

In Haskell this would look like

\x -> (find (<= head x) (show 521)) : (map (const '0') (tail x))

Answer 15

JavaScript (V8), 62 bytes

n=>(e=Math.log10(n)|0,x=n/(y=10**e),y*((x>=5)*5||(x>=2)*2||1))

Try it online!

Answer 16

Retina 0.8.2, 15 bytes

T`3-9`225
\B.
0

Try it online! Link includes test cases. Explanation:

T`3-9`225

Change 3 and 4 to 2, and higher digits to 5.

\B.
0

Change all digits after the first to 0.

Answer 17

05AB1E, 13 12 10 9 bytes

LR.ΔRTÑQO

-2 bytes by porting @JoKing's Raku answer, so make sure to upvote him as well!
-1 byte by taking inspiration from @Zgarb's second Husk answer.

Try it online or verify almost all test cases (times out for the larger test cases).

Explanation:

L          # Push a list in the range [1, (implicit) input-integer]
 R         # Reverse it
  .Δ       # Find the first value which is truthy for:
    R      #  Reverse the integer
           #   i.e. 200 → "002"
     T     #  Push 10
      Ñ    #  Pop 10 and push its divisors: [1,2,5,10]
       Q   #  Check for each if it's equal to the reversed integer
           #   "002" → [0,1,0,0]
        O  #  Take the sum of those checks (only 0 or 1 will be truthy at a time,
           #  and 10 is never truthy because no integer had leading 0s)
           # (after which the result is output implicitly)

Answer 18

brainfuck, 78 69 66 bytes

-[<+>>+>+<<-----],++<[->-<]>[-[-[-[>+++<[-]]]]>+<]>--.>--->,[<.>,]

Try it online!

-9 bytes by rearranging the variables and adding the output directly to the ASCII value.

-3 bytes by calculating and triplicating the constants in a single loop

[tape: 51, input (of first digit), output + 51, 51, input (of other digits)]
-[<+>>+>+<<-----]       51 0 51 51
,++<[->-<]              input minus 49("1")
>[                      if not input = 1
  -[-[-[                    if not input between 2 and 4
    >+++                        add 3 to output (will add another 1 later)
    <[-]                        set input = 0 
  ]]]                       exit if
  >+<                       inc output ("4" if input between "2" and "4" | "7" if input not between "1" and "4")
]
>--.                    decrement output by 2 and print it
>---                    set third 51 to 48("0")
>,[                     while more characters in input
  <.>                       print "0"
  ,                         read next input char
]

Answer 19

Rockstar, 163 ... 119 117 97 bytes

listen to N
cut N
roll N in D
X's 5
until X's as low as D
let X be/2
turn down X

say X*10*N or X

Try it (Code will need to be pasted in)

Answer 20

Wolfram Language (Mathematica), 45 bytes

Max@Select[{1,2,5}10^⌊Log10[s=#]⌋,#<=s&]&

Try it online!

Answer 21

C (gcc), 40 39 32 bytes

f(n){n=n>9?10*f(n/10):5>>5/-~n;}

Try it online!

Recursively calls itself, multiplying the returned value by \$10\$ and chopping the last digit off \$n\$ until \$n\$ is \$9\$ or less. Then returns one of \$\{1,2,5\}\$, whichever lays just below or equal to \$n\$ using xnor's formula.

Answer 22

sed 4.2.2, 25

• Thanks to @David258 for suggesting the use of 2g to start replacing at the 2nd match and saving a byte.

Pretty much the same as the perl answer. Sadly the sed y command is not as flexible.

s/./0/2g
y/346789/225555/

Try it online!

Answer 23

Brain-Flak, 116 bytes

({}<<>(((((()()()){}){}){}){})<>{{}<>(({}))<>}>)({}<>[({})<((((((((({}<>())())))()()())))))>[]]){({}()<{}>)}{}({}<>)

Try it online!

This uses string IO. Meaning input is expected as a string and output is produced as a string. This works by replacing all the digits other than the lead with zeros and then mapping the lead to the three results.

Rather predictably for Brain-Flak the two biggest sinks are

1. Producing the ascii code for 0

2. Mapping 9 different values to arbitrary outputs.

The first part which replaces everything with zeros is:

({}<<>(((((()()()){}){}){}){})<>{{}<>(({}))<>}>)

With most of it being the code for point 1:

(((((()()()){}){}){}){})

Answer 24

Pip, 25 bytes

@(_<=aFI[5 2o]*t**(#a-1))

A simple solution with filtering.

Explanation

@(_<=aFI[5 2o]*t**(#a-1))
               t**(#a-1)  ten to the power (length of input - 1) 
        [5 2o]*           times the list [5,2,1]
  _<=aFI                  Filtered by lambda: element <= input?
@(                      ) first element of filtered list

Try it online!

Answer 25

Octave, 43 bytes

@(x)y((y=[5 2 1]*10^floor(log10(x)))<=x)(1)

Try it online!

This converts the number to the highest power of 10 less than the number, then multiplies by 5, 2, and 1 to get the possible notes that could be involved. It then finds the largest note still less than the number.

---

It should be noted that Octave is very doubley and not really friends with 64bit integers. As a result numbers larger than 2^53 don't reliably work due to double precision issues. This may invalidate the answer.

---

---

The below answer is valid only if it is allowed to take the input as a string, and return a string, overcoming the double precision issues.

Octave, 41 bytes

@(x,y='521')[y(x(1)>=y)(1) 48+x(2:end)*0]

Try it online!

Answer 26

JavaScript, 30 29 bytes

I/O as an array of digits.

Uses xnor's formula for the first digit so please be sure to upvote him if you're upvoting this.

a=>a.map((x,y)=>y?0:5>>5/-~x)

Try it online!

Answer 27

Bash, 39 36 bytes

Saved 3 bytes thanks to Digital Trauma!!!

echo $[(5>>5/-~${1::1})*10**~-${#1}]

Try it online!

Port of my C answer.

Explanation:

echo $[(5>>5/-~${1::1})*10**~-${#1}]  
     $[                            ]   # Evaluate what's inside as an  
                                       #   arithmetic expression  
       (5>>                            # Shift 5 to the right by
           5/                          #   5 integally divided by
             -~                        #     1 plus
               ${1                     #      the first argument's
                  ::1})                #        substring starting at 0 of length 1   
                       *               # Times  
                        10**           #   10 to the power of   
                              ${#1}    #     the length of the first agument
                            ~-         #       minus 1

Answer 28

Brachylog, 25 bytes

{≥.~×Ċ{~^h10}ᵗh∈125∧≜}ᵘot

Try it online!

How it works

{≥.~×Ċ{~^h10}ᵗh∈125∧≜}ᵘot
{                    }ᵘ   find all unique outputs of …
 ≥.                         the output is less-equal the input,
   ~×Ċ                      and two numbers which product is the output, where
      {~^h10}ᵗ                the 2. number can be obtained by 10^k,
              h∈125           the 1. number is one of 1, 2, 5
                   ∧≜       return the output with the constrains solved
                       ot order all possible banknotes and take the largest

Answer 29

x86-16 machine code, IBM PC DOS, 34 31 30 bytes

00000000: d1ee ad8a c849 b830 0acd 10ac 3c35 7c04  .....I.0....<5|.
00000010: b035 eb07 3c32 b032 7d01 48cd 29c3       .5..<2.2}.H.).

Listing:

D1 EE       SHR  SI, 1          ; SI to DOS PSP 
AD          LODSW               ; AL = input length 
8A C8       MOV  CL, AL         ; input length into CL
49          DEC  CX             ; remove leading space from length
B8 0A30     MOV  AX, 0A30H      ; AH = 0AH, AL = '0' 
CD 10       INT  10H            ; display '0' CX number of times 
AC          LODSB               ; AL = first digit 
3C 35       CMP  AL, '5'        ; is it less than five? 
7C 04       JL   LT_FIVE        ; if so, check two 
B0 35       MOV  AL, '5'        ; otherwise it's a 5 spot 
EB 07       JMP  DONE           ; jump to display
        LT_FIVE: 
3C 32       CMP  AL, '2'        ; is it less than two? 
B0 32       MOV  AL, '2'        ; if not, it's a 2 
7D 01       JGE  DONE           ; jump to display 
48          DEC  AX             ; otherwise it's a '1'
        DONE:
CD 29       INT  29H            ; display first digit of denomination 

C3          RET                 ; return to DOS

Try it online! (type ASM 1, ASM 9, etc)

Looks at the first digit and determines if it's less than 5 or 2 and resets it to the appropriate note digit. Then displays the remaining length of the input string as 0's.

Standalone PC DOS executable COM program. Input via command line, output to console.

Answer 30

Thunno 2 t, 5 bytes

ærTFƇ

Try it online!

Note: this is pretty slow (the 729871 case takes ~5s on my computer and ~10s on the online interpreter) because it checks every number in the range \$[1 .. \text{input}]\$.

Explanation

ærTFƇ  # Implicit input
æ      # Filter [1..input] by:
 r     #  Reverse it
  TF   #  Push the factors of 10
       #   -> [1, 2, 5, 10]
    Ƈ  #  And check if the reversed
       #  integer is in this list
       # Implicit output of last
       # (largest) integer