22
\$\begingroup\$

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
\$\endgroup\$
16
  • 7
    \$\begingroup\$ You're going to need to give us the full list, without it it'll be pure guesswork on our part what "etc." represents. \$\endgroup\$
    – Shaggy
    Sep 7 '20 at 14:22
  • 4
    \$\begingroup\$ If you are mentioning a rule in the comments, please add them to your question. It's a good practice that will welcome correct answers. \$\endgroup\$
    – Razetime
    Sep 7 '20 at 14:35
  • 12
    \$\begingroup\$ Suggested formula to describe the notes: \$m\times 10^n,\:m\in\{1,2,5\},\:n\ge 0\$ (see the Mathjax code for this). I don't think an upper limit on \$n\$ should be explicitly defined as the values that can be supported depend on the language anyway. \$\endgroup\$
    – Arnauld
    Sep 7 '20 at 15:23
  • 5
    \$\begingroup\$ The input will be less than 10^19 It looks like you're assuming the languages support 64-bit unsigned integers or higher, given that 2^63 < 10^19 < 2^64. It has the effect of unnecessarily penalizing languages that do not natively support such large integers. Note that, on this site, we usually allow solutions to use whatever native number type is available to the language of choice, as long as it does not fall into the category of abuse. \$\endgroup\$
    – Bubbler
    Sep 8 '20 at 0:35
  • 3
    \$\begingroup\$ By the way, congrats on this challenge! You not only got it reopened, but got it made a HNQ! It was also pretty fun to make a solution for :D \$\endgroup\$ Sep 8 '20 at 12:33

33 Answers 33

15
\$\begingroup\$

Python 2, 39 bytes

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

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Almost exactly what I had in JS. :-) \$\endgroup\$
    – Arnauld
    Sep 7 '20 at 21:44
12
\$\begingroup\$

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!

\$\endgroup\$
1
  • 4
    \$\begingroup\$ Nice answer! If you borrow the \B from the Retina answer and swap the order, your second answer comes in at 19 bytes: Try it online! \$\endgroup\$ Sep 8 '20 at 5:45
9
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Too bad I. is off by one for this problem. \$\endgroup\$
    – Bubbler
    Sep 8 '20 at 1:31
6
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ I tried using signif but didn't work so far \$\endgroup\$
    – JayCe
    Sep 7 '20 at 22:45
  • \$\begingroup\$ I think %/%1 is shorter than floor by a byte. \$\endgroup\$
    – Giuseppe
    Sep 8 '20 at 1:04
  • \$\begingroup\$ try this \$\endgroup\$
    – Giuseppe
    Sep 8 '20 at 1:06
  • 2
    \$\begingroup\$ 47 bytes \$\endgroup\$
    – Giuseppe
    Sep 8 '20 at 1:13
  • \$\begingroup\$ @Giuseppe Of course this makes way more sense to use nchar. \$\endgroup\$
    – JayCe
    Sep 8 '20 at 1:38
6
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ Looks like you can save a few bytes by skipping the assignments to D, E & F, using the actual values in the if statements and assigning them directly to G \$\endgroup\$
    – Shaggy
    Sep 9 '20 at 11:57
  • \$\begingroup\$ And the second line can be let C be B at 0 to save another couple of bytes. \$\endgroup\$
    – Shaggy
    Sep 9 '20 at 13:40
  • \$\begingroup\$ Hope you don't mind but, after some further golfing, I went ahead an posted my own solution. Happy to delete if you do, though. (By the way, your byte count is 202) \$\endgroup\$
    – Shaggy
    Sep 9 '20 at 14:20
  • \$\begingroup\$ @Shaggy be my guest, I rarely have time for a bit of PPCG so had a quick bash at it, always interesting to see techniques other people use to golf things down more \$\endgroup\$
    – Darren H
    Sep 10 '20 at 12:50
5
\$\begingroup\$

Charcoal, 12 bytes

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

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

 S             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
\$\endgroup\$
5
\$\begingroup\$

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).
\$\endgroup\$
2
  • \$\begingroup\$ Why on Earth is that a built-in?! \$\endgroup\$
    – Shaggy
    Sep 9 '20 at 21:52
  • 3
    \$\begingroup\$ @Shaggy Not sure. It was added by Leo at some point as "money values", so I guess he anticipated challenges like this one. \$\endgroup\$
    – Zgarb
    Sep 10 '20 at 8:43
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ You may want to add in your explanation that -h prints the last value in the list. I was confused for a moment why just a filter was enough before I noticed the flag. :) EDIT: Ah oops, I see "Implicit output of last element" now, my bad. \$\endgroup\$ Sep 8 '20 at 7:56
4
\$\begingroup\$

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!

\$\endgroup\$
2
  • 5
    \$\begingroup\$ People appreciate explanations, even for answers that are not golfed well. No need to strike them out. Just keep your best answer on top. \$\endgroup\$
    – Razetime
    Sep 8 '20 at 1:24
  • \$\begingroup\$ Also 21 bytes. Could have been 20 if Pyth had a builtin for less than or equal to. \$\endgroup\$
    – hakr14
    Feb 2 at 4:30
4
\$\begingroup\$

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))
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ How did it let me post this answer? The question closed three minutes ago. \$\endgroup\$ Sep 7 '20 at 15:12
  • 1
    \$\begingroup\$ Maybe because you didn't refresh your page? Or maybe it's just that your answer's too good :) \$\endgroup\$
    – user
    Sep 7 '20 at 15:13
  • 2
    \$\begingroup\$ @RedwolfPrograms impressively short :) \$\endgroup\$
    – stephanmg
    Sep 7 '20 at 15:17
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Great approach! \$\endgroup\$
    – Luis Mendo
    Sep 7 '20 at 23:50
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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
]
\$\endgroup\$
3
\$\begingroup\$

Rockstar, 163 ... 119 117 bytes

listen to X
Z's5
until Z is as weak as X at 0
let Z be/2
turn down Z

Y's1
while X at Y
let Z be*10
let Y be+1

say Z

Rockstar doesn't seem to work on TIO but you can paste the programme and input into their own interpreter to test it.

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 45 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can save 1 char with by using 2g to replace from the second match instead of \B i.e. s/./0/2g. which is an advantage over Perl! \$\endgroup\$
    – David258
    Sep 9 '20 at 13:34
2
\$\begingroup\$

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:

(((((()()()){}){}){}){})
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You might need to flip the ternary statement and change the condition to n<10, it currently fails with 95. \$\endgroup\$ Sep 7 '20 at 23:43
  • \$\begingroup\$ Thanks, @MatthewJensen, I'd forgotten to floor the division on the recursive call. \$\endgroup\$
    – Shaggy
    Sep 8 '20 at 8:51
1
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 3 bytes shorter \$\endgroup\$ Sep 8 '20 at 18:40
  • \$\begingroup\$ @DigitalTrauma Nice use of the deprecated $[] notation and the default substring starting position - thanks! :-) \$\endgroup\$
    – Noodle9
    Sep 8 '20 at 18:57
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

enter image description here

\$\endgroup\$
0
\$\begingroup\$

><>, 41 bytes

1$:a(?v:a%-a,$a*!
&v?=1:/~$?)4&52
 <;n *<

Try it Online!

The first line is a loop, bringing down the number to a single digit through the usual :a%-a, process. At the same time, the magnitude is transferred to another number on the stack.

As always, branching gets verbose, and with no floor function, two conditionals are needed.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.