# 2 solutions in python - detailed explanation with video

• 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":

``````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
``````
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!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.