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

Jelly, 9 bytes, slow

DUḌ⁵%
’Ç¿

Try it online!

’Ç¿     Decrement input while…

DUḌ     The number with digits reversed (12300 → 321)
   ⁵%   is not a divisor of 10 (10 % n is truthy).

Jelly, 11 bytes, fast

DḢRg⁵ṀṁDŻIḌ

Try it online!

DḢR           range [1..first digit]
   g⁵         gcd each with 10
     Ṁ        maximum
      ṁD      reshape like original digits (e.g. [2,2,2,2,2])
        ŻI    prepend 0, get increments (e.g. [2,0,0,0,0])
          Ḍ   digits to number

This uses the fact that mapping \$[1 \dots 9]\$ to \$[1,2,2,2,5,5,5,5,5]\$ is achieved by $$ n \mapsto \max_{1 \leq k \leq n} \gcd(k, 10). $$

Porting xnor's 5>>5/-~n formula is six bytes ‘5:5æ», but the above is only four Rg⁵Ṁ.

Answer 2

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

Answer 3

Befunge-93, 58 bytes

~:"4"`!#v_"5">,~1+#v_@
v     >#< "2"^"0"  <
>"1"`#^_  "1"^

Try it online!

How does it work?

(This is essential the same as Xcali's second Perl solution)

We first look at the first character, if it's greater than 4, we print 5, if it's greater than 1 we print 2, else we print 1. Then, for each following character on the input, we print a 0:

~:"4"`!#v_"5">,        # If the first character is greater than 4, print a 5

~:"4"`!#v_   >,        # If the first character isn't greater than 4,
v     >#< "2"^         # but is greater than 1, print a 2
>"1"`#^_ 

~:"4"`!#v_   >,        # If the first character isn't greater than 4,
v     >#<    ^         # and isn't greater than 1, print a 1
>"1"`#^_  "1"^   

>,~1+#v_@              # In a loop (mind, the loop is entered at the ~)
^"0"  <                # for each character on the input, print a 0;
                       # terminate the program when there is no more input.

Answer 4

SimpleTemplate 0.84, 76 bytes

Yeah, it is ... big ...
One of the longest answers here, but it works!

It uses a simple lookup variable, to know which digit to show.
Then, a simple regular expression separates the first digit and the rest.
A loop just writes out all the zeroes needed.

{@setX"1122255555"}{@ifargv.0 matches"@(\d)(.*)@"M}{@echoX.[M.1]}{@eachM.2}0

Notice that the input can be a number or a string: it will be handled as a string anyway. But be aware of PHP's integer precision.

---

Ungolfed:

To make it a bit more readable, here's an ungolfed version:

{@set initial_digit 1, 1, 2, 2, 2, 5, 5, 5, 5, 5}
{@if argv.0 matches "@(\d)(.*)@" match}
    {@echo initial_digit.[match.1]}
    {@each match.2 as digit}
        {@echo 0}
    {@/}
{@/}

Consideration points:

• initial_digit can be a string or an array, as both can have their elements indexed the same way.
• match.0 isn't used because it has the whole matched input, while match.1 and match.2 have the content of their respective groups.
• {@echo 0} and 0 have the exact same function: output 0.
  Any non-whitespace and all characters that arent in a valid instructions are outputted directly.
• {@each match.2 as digit} and {@eachM.2} loop over all characters in match.2 or M.2, being a lot shorter than a repeat.
• To convert to a function, just wrap it in an {@fn ...}[...]{@/}.
  For the golfed version, all missing {@/} must be added for the code to work properly.

---

You can try this on: http://sandbox.onlinephpfunctions.com/code/a45b85003e2d495c796046b000326fb1b5e50423

Answer 5

><>, 25 bytes

i\{c%:4)3*$1)++>n<
?\i0(:

Try it online!

Answer 6

Desmos, 50 bytes

d=[5,2,1]
a=10^{\floor(\log n)}
f(n)=ad[d<=n/a][1]

Try it on Desmos!

Finds the greatest value in \$[1,2,5]\$ less than the first digit of \$n\$ and multiplies it by \$10^{\lfloor\log_{10}n\rfloor}\$