Next number with k fives

Question

Challenge:

Your program will take two integers n and k as input, and output the smallest integer greater than (but not equal to) n that contains at least k occurrences of the digit 5.

You can assume 1 ≤ k ≤ 15 and 1 ≤ n < 10**15.

This is a restricted-time challenge. Your program must run on TIO for all of the test cases and complete within 10 seconds in total.

General rules:

• This is code-golf, so the shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for any programming language.

• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call. The function parameters may be taken in either order, but please specify in your answer.

• Default Loopholes are forbidden.
• You must add a link with a test for your code (i.e. TIO).
• The answer header should list the score in bytes but also the total time taken for all test cases on TIO
• If your language is not on TIO, the code should finish far under 10 seconds on your machine so that you're confident it's fast enough on any reasonable computer.
• Adding an explanation for your answer is highly recommended.

Test Cases:

(n, k) ->  output
(53, 2) -> 55
(55, 1) -> 56
(65, 1) -> 75
(99, 1) -> 105
(555, 3) -> 1555
(557, 1) -> 558
(5559, 3) -> 5565
(6339757858743, 5) -> 6339757859555
(99999999999999, 15) -> 555555555555555

Program Example:

This program is correct.

Answer 1

R + stringr, 85 84 76 bytes, .062s on TIO

f=function(n,k,m=2+stringr::str_count(n+1,"5")-k)`if`(m<2,f(n+.1^m*2,k),n+1)

Try it online!

-1 byte thanks to Robert S.
-8 bytes thanks to Giuseppe.

A simple recursive solution would be to increment by 1 until the answer is found, but this would not meet the time restriction. To meet the time restriction, this function makes use of the fact that if there are p missing 5s, we can increment by 2*10^(p-2).

Note that when p=1, the increment becomes 0.2. This is OK, since after 5 steps we come back to an integer, and none of the decimal numbers encountered in the mean time have an extra 5. If instead we were to increment by 5*10^(p-2) or by 1*10^(p-2), then we would find f(24, 1)=24.5 instead of 25 for example.

Answer 2

Jelly, 37 bytes 0.113 s on TIO

»DL‘Ɗ}©5xḌ_DḌÐƤ;®ŻṬ€UḌ¤+⁹D=5S>ʋƇ⁸’¤ḟṂ

Try it online!

This works by

1. working out the maximum of the number of digits in the input plus one and k, and making a number with that many fives
2. Subtracting the input from that number
3. Generating all of the suffixes of that number
4. Also generating all the powers of ten from 1 up to the next one greater than the input
5. Adds each of the numbers in 3 and 4 to the input
6. Removes answers with too few 5’s
7. Filters out the input from the answers
8. And returns the minimum

Answer 3

05AB1E, 33 32 bytes

sg>‚à©5s×α.s0š®Ý°0šâO+IKʒ§5¢¹@}ß

Port of @NickKennedy's amazing approach in his Jelly answer, so make sure to upvote him!!

Takes $k$ as first input; $n$ as second.

Try it online or verify all test cases.

Explanation:

sg>                # Get the length+1 of the second (implicit) input-integer
   ‚à              # Pair it with the first input-integer, and leave the maximum
     ©             # Store this maximum in the register (without popping)
      5s×          # Create an integer (actually, create a string..) with that many 5s
         α         # Take the absolute difference with the second (implicit) input
          .s       # Get the prefixes of that number
            0ª     # Prepended with an additional 0
    ®              # Get the maximum from the register again
     Ý             # Create a list in the range [0, max]
      °            # Raise 10 to the power of each integer
       0ª          # And also prepend an additional 0 to this list
              â    # Then create each possible pair of these two lists
               O   # Sum each pair
                +  # Add the second input to each sum
IK                 # Then remove the second input from this list (if present)
  ʒ                # And filter this list by:
   §               #  Cast the number to a string (bug, shouldn't be necessary)
    5¢             #  Count the amount of 5s in the string
      ¹@           #  And check if this count is larger than or equal to the first input
        }ß         # After the filter: only leave the lowest number
                   # (which is output implicitly as result)

Answer 4

Stax, 17 bytes (6.861 total seconds on TIO)

≈ª╞¥é£ôñτ←╝α┴╢JLd

Run and debug it

This program takes k and n on standard input separated by space. Stax doesn't have a convenient way to run multiple test cases on TIO, so I ran each input separately and added up the time. 99% of the time is in the interpreter process startup. Using the javascript interpreter on staxlang.xyz, all test cases run in 50 milliseconds.

Last test case on Try it online!

Procedure:

1. Increment input
2. If there are enough 5s, terminate and print
3. t= number of trailing 5s in the number
4. Add 10 ** t
5. Goto 2

Answer 5

Python 2, 70 68 bytes (.025 seconds on TIO)

l=lambda n,k:'5'*k*(10**~-k>n)or-~n*(`n+1`.count('5')>=k)or l(n+1,k)

Try it online!

This might be a bit of a stretch; it is correct in all cases, and finishes in negligible time for the test cases, but doesn't finish in reasonable time for some other cases. It technically meets the requirements though.

In short, if the smallest number with k fives is larger than n, we use that number since it is obviously the correct solution. If it isn't, we resort to the standard recursive approach.

Answer 6

Python 3, 144 98 86 75 bytes

f=lambda N,k,d=1:k>str(-~N).count("5")and f(N+-(-~N//d+5)%10*d,k,d*10)or-~N

Try it online!

This is $\mathcal{O}(k)$, (system time .008 on TIO) and has golfed well with some advice from ASCII-only.

The algorithm is to round up each digit (starting from the least-significant one) to the nearest value of 5 until the new number's decimal representation has the desired count.

The original approach used an abortable (D=iter(range(k)) and list(D) at work here) list comprehension, but @ASCII-only has convinced me that will never win code-golf. I dislike recursion, but if the algorithm is written to minimize recursion-depth, then a future compiler/interpreter will be smart enough to re-implement it as a while loop.

Answer 7

Perl 5 -pl, 44 bytes

$k=<>;$_++;s/.*?(?=5*$)/1+$&/e while$k>y/5//

Try it online!

Finds what the number is without its trailing 5s. Increments that portion by 1. Continues until sufficient 5s are in the number. Takes about .012s on TIO to run all test cases.

Answer 8

Python 3, 59 bytes

Recursive solution. Recursion depth is a problem(has to be changed for higher numbers), but it is correct.

lambda x,k:eval(("f(x+1,k)","x+1")[str(x+1).count("5")==k])

Try it online!

Answer 9

Python 3, 72 bytes

def f(n,k):
 while(1):
  n+=1
  if str(n).count('5')>=k:return n

Try it online!

Answer 10

Java 8, 69 bytes, 60+ seconds on TIO with the last test case, ~1.5 seconds without.

(n,k)->{for(;(++n+"").chars().filter(i->i==53).count()<k;);return n;}

Anyone have any ideas on how to pass the last test case?

Answer 11

PHP, 109 97 bytes, (< 0.03s on TIO)

function($n,$k){++$n;do if(count_chars($n)[53]>=$k)return$n;while($n+=10**strspn(strrev($n),5));}

Try it online!

Based on @recursive's algorithm.

Answer 12

Retina, 63 bytes

.+$
*
^.+
$.(*__
/((5)|.)+¶(?<-2>_)+$/^+`^.*?(?=5*¶)
$.(*__
1G`

Try it online! Takes n and k on separate lines, but link includes header that converts the test suite into the appropriate format. Explanation:

.+$
*

Convert k to unary.

^.+
$.(*__

Increment n. The * repeats its right argument (here the first _ character) the number of times given by its left argument (which, as here, defaults to the match). This results in a string of that length. The $( (the ) is implied) then concatenates that with the second _ and the . causes the resulting length to be taken. (Actually Retina 1 is cleverer than that and just performs the calculation on the underlying lengths in the first place.)

/((5)|.)+¶(?<-2>_)+$/

Test whether enough 5s can be found in n to match the _s of the unary representation of k. This test has been golfed and would be three times faster with ^ added after the initial / and faster still if [^5] was used instead of ..

^+`

Until the test passes...

^.*?(?=5*¶)
$.(*__

... increment n but exclude trailing 5s.

1G`

Delete k.

Answer 13

Clam, 30 bytes, ~0.2s on TIO

=Q+r1=qC5R1?<qQ[=qrw<n#:q5QqiQ

Transpiles to this JS (full test suite added for timing of course), where inputs is an array of the inputs (n first, k second)

Thanks @ArBo for the approach

Explanation

=Q+r1=qC5R1?<qQ[=qrw<n#:q5QqiQ - Implicit Q = first input
=Q+r1                          - Q = next input (1st input) + 1
     =qC5R1                    - q = 2nd input 5s (eg 555 for k=3)
           ?<qQ[               - if q < Q...
                =qr            -   q = next input (2nd input)
                   w           -   while...
                     n         -     length of...
                      #:q5Q    -       Q.filter(q=>q==5)
                    <          -     is less than...
                           q   -       q
                            iQ -     Increment Q
                               - Implicit output of Q

Answer 14

C (gcc), 159 158 152 150 149 bytes, ~0.04 s

Outputs the answer to STDOUT, with leading zeroes.

-3 byte thanks to ceilingcat

m,j;f(n,k)long n;{char*t,s[17];for(t=s+sprintf(s,"%016ld",++n),m=n=0;m<k&--t>s;m<k&&*t-53?n=*t>53,*t=53:0)for(*t+=n,m=j=17;j--;)m-=s[j]!=53;puts(s);}

Try it online!