You are given a number x. you have to find the minimum number of steps required to reach n from 1. At a particular point, you have two choices

1) increment the number by 1

2) reverse the integer (remove leading zeros after reversing)

eg: n=42

sol: 1>2>3>4>5>6>7>8>9>10>11>12>13>14>41>42 (15 steps)

The minimum steps to reach 42 from 1 is 15. This can be achieved if we increment numbers by 1 from 1 to 14 (13 steps). After reaching 14 we can reverse the number which will give us 41 (1 step). From 41 we can increment number by 1 to reach 42(1 step). hence total 15 steps which is then minimum

Note that if we reverse the number after reaching 12 or 13, we will not get the minimum steps

1>2>3>4>5>6>7>8>9>10>11>12>21>22>23>32>33>34>35>36>37>38>39>40>41>42 (25 steps)

eg: n=16

sol: 1>2>3>4>5>6>7>8>9>10>11>12>13>14>15>16 (15 steps)

In this case we have to increment the numbers till 16 which will give us the minimum of 15 steps.

Constraints:- 1<=n<=10^14.

I can only think of BFS/DP here which doesn't look like optimal solution.