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.
Can you provide the link to this problem ?
This was asked in Nutanix hiring test. I don't have any link.
Edit:- Looks like this was posted in leetcode as well ( https://leetcode.com/discuss/interview-question/417725/Nutanix-University-Round-Questions ). But no answers in that thread.
Let's say the goal is $$$n = 5280$$$. There must be some first moment when we get a 4-digit number and the only possibility is that we increase by one from $$$999$$$ to $$$1000$$$. With the same logic, we must take a step from $$$99$$$ to $$$100$$$ before. So the problem breaks into: how to get from $$$100$$$ to $$$999$$$ optimally (and similar for smaller number of digits), and how to get from $$$1000$$$ to $$$5270$$$. I guess that both parts are about the sum of two halves of a number (first one is reversed). So, I would get $$$5270$$$ from $$$1000$$$ by $$$25$$$ increments first, then reverse, then another $$$70-1 = 69$$$ increments. That's my idea, maybe there are some issues with this.
Thanks for the answer. However, I am not able to prove that your method will indeed give the optimal answer.
Based on Errichto's hint, I came up with this solution. I don't know if it is right or not, but I think it is.
Let's call all numbers which are of the form
10 ^ r
as base numbers. To reach a numberX
from1
, we first reach a base number having the same number of digits asX
. E.g. to reach32463
, we first reach10000
using some operations. Only then do we think about reaching32463
.How do we reach a base number? To reach
1000
, you must reach999
and then increment1
. It is the only way to increase the number of digits. Reversing a number won't help. This brings us back to the question of reaching some number X (999
) from a base number (100
) and so on.To reach
32463
from10000
, we observe that it is optimal to use the reverse operation at most once. This operation is preceded and followed by some number of increment operations. Thinking backward, we need to solve for32461
(with last digit1
) and then increment twice to reach X =32463
. The last digit1
is preserved when we reverse our number. Now for the remaining 4 digits to the left of 1. If we add6
(tens' place) before reversing, then we shall be adding6 * 10 ^ 3
to our base number. It is better to add this digit after the reversal, i.e., we will need only to add6 * 10 ^ 1
. By this logic, the first two digits should be added before the reverse operation and the later half afterward. The whole series of operations looks like this:To reach from
10000
->99999
, we use the same logic. First, we reach10000
->10099
, reverse to99001
, and then go99001
->99999
.It's a simple pattern with the number of 9s being divided equally into both sides of the reverse operation.