2 solutions in python - detailed explanation with video


  • 1

    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 1s into 0s in binary
    • shift right
    • repeat until we reach n=1

    Examples on how to "convert tail 1s into 0s":

    1. 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
    
    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!


Log in to reply
 

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