Bit Manipulation solution


  • 0
    P
    var helper = function(n,count) {
        if(n<=3) {
             return count+(n-1)
        }
    
        if (n%2==0) {
            count++;
            return helper(n/2, count)
        }
        else {
            count++;
            var nmin1 = (n-1).toString(2).split("1") // Basically, it converts n-1 to its bit representation and splits it by finding 1 to form an array. Eg: 20 would bre represnted as "10100" and after split it becomes ["0", "00"]
            var nmin1Zeros = nmin1[nmin1.length-1].length
            
            var nmin2 = (n+1).toString(2).split("1")
            var nmin2Zeros = nmin2[nmin2.length-1].length
    
            if(nmin1Zeros>=nmin2Zeros) { // If n-1 has more 0's after the last 1 in bit representation, its more divisible by 2. Hence we can get to 1 faster.
                return helper(n-1, count)
            }
            return helper(n+1, count)
        }
    }
    var integerReplacement = function(n) {
       var count=0;
       return helper(n,count)
    };

Log in to reply
 

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