Find the number formed by sorted digits that is closest to and smaller or equal to n.

Question

I am looking for an algorithm that takes a number N as an input and outputs a number with base 10 that is:

1. The closest number to N
2. Made out of sorted digits from the smallest to the highest
3. And smaller or equal to N

Example:

Input -> Output

132 -> 129

1000 -> 999

111111111111111110 -> 99999999999999999

7 -> 7

Answer 1

1. Locate the leftmost place in the number where a smaller digit follows a larger:

   ......ab...
   

   with $a>b$.

2. Replace the first digit $a$ in the number with $a-1$ and all following digits with $9$.

For example, in 111333555777444333888, $ab$ is $74$, so we replace the first $7$ by $6$ and the rest with nines:

in:  111333555777444333888
out: 111333555699999999999