15
In this challenge, you are given a number x. You have to find the minimum number of steps required to reach x 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)
Input: n=42
Output: 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 the total number is 15 steps, which is then the 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)
Input: n=16
Output: 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 until we get 16, which will give us a minimum of 15 steps.
Note: Starting from 0 is also allowed, which will increase all output by 1.
7Nice challenge but it needs test cases and a clearly defined rules. – Jonah – 2019-11-01T15:14:00.777
What's
reverse(reverse(10))
andreverse(2)
? – girobuz – 2019-11-01T22:16:54.3901@girobuz reverse(10) will be 1 (After removing leading zeros) - I had missed it earlier. have added it in the second step. so reverse(reverse(10)) will be reverse(1) which is 1. reverse(2) -> 2 – adam – 2019-11-01T23:07:17.747
Your counter-example (25 steps to reach 42) could be reduced to
1>2>3>4>5>6>7>8>9>10>11>12>21>22>23>24>42
(16 steps), which is still more than the correct solution (15 steps), but... less worse :-) – Phelype Oleinik – 2019-11-02T15:43:45.457Can any one prove that: $ reversed(n) > n \implies stepTo(reversed(n)) \ge stepTo(n) $? I saw many answers assumed this. – tsh – 2019-11-04T10:42:49.253
May we use 0-indexing? – Jitse – 2019-11-04T14:18:25.183
2yes, we can use 0 based-indexing. in that case, the answer will increment by one – adam – 2019-11-05T09:30:22.807