347 - Run

Difficulty : medium

Solution Description :

DP brute force problem

Condition of runaround number
1. Must be distinct digit and all digit between 1 and 9.
    10 is not runaround number. Because 0 is wrong digit for runaround number.
    11 is not runaround number. Because 1 comes two times.
    15 is runaround number.
2. Staring and ending position are 0 (first digit).

pre-generate all runaround number up to 9682415. In this problem the input value less than 9682416.
Use bottom to top approach for pre-generate the runaround number and store to array a[].

Example (bottom to top approach):
From 15 to 10
a[15] = 15  //15 is runaround number
a[14] = 15 // 14 is not runaround number. so, set the previous runaround number to 14 position.
a[13] = 13
a[12] = 13
a[11] = 13
a[10] = 13

You got 457 runaround number between 1 and 9682415 inclusive.

Now, input n and print a[n]