Problem A. As simple as it gets

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  


Let us define that a positive integer A is simpler than a positive integer B if the decimal representation of A requires less different digits than the decimal representation of B.

For example, number 55 is simpler than 12 which in turn is simpler than 123.

Your program will be given a number N and must find the largest integer X such that X < N and X is simpler than N.

Input file format

Input file contains integer N.

Output file format

Output file must contain integer X. If there is no integer simpler than N, output file must contain 0 (zero).


1 ≤ N ≤ 231 − 1

Sample tests

No. Input file (input.txt) Output file (output.txt)


Obvious solution is to decrement the number until a simpler one is obtained. This solution may require O(N × log N) operations which is too slow.

To improve that, we need to work with decimal representations N = n1 n2… nK and X = x1 x2… xM.

The definition of X < N gives us two cases:

  1. M < K,
  2. M = K and there exists some p such that x1 = n1, x2 = n2, …, xp − 1 = np − 1 and xp < np

In the first case the condition of maximum possible X leads us to M = K − 1 and x1 = x2 = …  = xK − 1 = 9.

In the second case the same condition allows us to conclude that all digits of X after the p-th one are equal (xp + 1 = xp + 2 = …  = xK). Indeed, if for some X these are different, we can replace them all with the largest of them to obtain X′ > X. The X will be as simple or simpler than X and still less than N.

Thus, all possible values of X can be searched by checking all combinations of p = 1… N, xp = 0… np − 1, xp + 1 = 0… 9. This solution requires O(q2 × log 2 N) operations, where q is the number representation base (q = 10 in this problem).

0.078s 0.009s 13