Hi!

### VIDEO EXPLANATION

This topic is deeply explained in the following youtube video, but you can find the summary below

### TRIVIAL, BROUTE-FORCE SOLUTION, 478 ms

The problem statement already hints on how task can be solved. Just follow instructions and explore all the options in a simple recursion:

```
class Solution(object):
def rec(self, n, steps):
if n <= 1:
return steps
if n % 2 == 0:
return self.rec(n/2, steps+1)
else:
return min(self.rec(n+1, steps+1), self.rec(n-1, steps+1))
def integerReplacement(self, n):
return self.rec(n, 0)
```

Although, this solution is accepted, it takes 478 ms and is definitely not the most optimal.

### 10x faster solution, 42 ms

If you look at the binary representation of possible values of `n`

, and remember that dividing by 2 is just shifting right by 1 in a binary representation, then you may notice that the fastest way to get to 1 would be to:

- "convert" tail
`1`

s into`0`

s in binary - shift right
- repeat until we reach n=1

Examples on how to "convert tail `1`

s into `0`

s":

- add 1

```
n=0111 0000b => need to shift to right 4 times
n=0111b => need to +1
n=1000b => need to shift right 3 times
n=1
```

- subtract 1

```
n=0010 0001b => need to -1
n=0010 0000b => need to shift right 5 times
n=1
```

So, we're intuitively doing the following:

- if rightmost binary digits are
`11`

, then we add 1 - if rightmost binary digits are
`01`

, then we subtract 1

The only exception to this rule is`n=3=11b`

:

```
11b --(+1)--> 100b --(2x shift)--> 1
11b --(-1)--> 10b --(1x shift)--> 1
```

So we can add the check for it, but the rest of the cases are ok to apply our logic, leading to the following code:

```
class Solution(object):
def rec(self, n, steps):
if n <= 1:
return steps
div2 = n/2
if n % 2 == 0:
return self.rec(div2, steps+1)
else:
if div2 % 2 == 0 or div2 == 1: # div2 == 1 covers n==3 exception
return self.rec(n-1, steps+1)
else:
return self.rec(n+1, steps+1)
def integerReplacement(self, n):
return self.rec(n, 0)
```

This solution takes only 42 ms and seems to be 10x faster than the previous one, but definitely 10x depends on the tests judge runs.

### FINAL THOUGHTS

I hope that the video was not too boring and long, but I made it to explain the whole process of solving this task as if you were coding on a whiteboard. This can be helpful for those who goes to onsite interviews soon. Anyways, please, leave comments here or below the video if you have them - I'll answer and improve! Good luck!