Inspired by this post over on Puzzling. Spoilers for that puzzle are below.
Given three positive integers as input, (x, y, z)
, construct the inclusive range [x, y]
, concatenate that range together, then remove z
not-necessarily-consecutive digits to produce the largest and smallest positive integers possible. Leading zeros are not permitted (i.e., the numbers must start with [1-9]
). Output those two numbers in either order.
For the example from the Puzzling post, for input (1, 100, 100)
, the largest number possible is 99999785960616263646566676869707172737475767778798081828384858687888990919293949596979899100
,
and the smallest number is 10000012340616263646566676869707172737475767778798081828384858687888990919293949596979899100
,
following the below logic from jafe's answer posted there:
- We can't influence the number's length (there's a fixed number of digits), so to maximize the value we take the maximal first digit, then second digit etc.
- Remove the 84 first non-nines (16 digits left to remove):
999995051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
- The largest number within the next 17 digits is 7, so from here, the next digit in the answer can be at most 7 (we can't remove more than 16 digits). So remove 15 non-7's... (1 digit left to remove):
999997585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
- From here, the next digit can be at most 8 so remove one non-8 from the middle:
99999785960616263646566676869707172737475767778798081828384858687888990919293949596979899100
- Similar logic, but reversed (i.e., we want leading
1
s instead of leading9
s) for the smallest number.
Here's a smaller example: (1, 10, 5)
.
We construct the range 12345678910
and determine which 5
digits we can remove leaving the largest possible number. Obviously, that means we want to maximize the leading digit, since we can't influence the length of the output. So, if we remove 12345
, we're left with 678910
, and that's the largest we can make. Making the smallest is a little bit trickier, since we can pluck out numbers from the middle instead, leaving 123410
as the smallest possible.
For (20, 25, 11)
, the result is rather boring, as 5
and 1
.
Finally, to rule out answers that try leading zeros, (9, 11, 3)
gives 91011
which in turn yields 91
and 10
as the largest and smallest.
I/O and Rules
- If it's easier/shorter, you can code two programs/functions -- one for the largest and one for the smallest -- in which case your score is the sum of both parts.
- The input and output can be given by any convenient method.
- The input can be assumed to fit in your language's native number type, however, neither the concatenated number nor the output can be assumed to do so.
- Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
- Standard loopholes are forbidden.
- This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.
9, 11, 3
would do. \$\endgroup\$