Java, 4ms, iterative, log(n), simple solution with explaination


  • 0
    A

    While shifting the number to the right, we count zeros once and ones twice for the LSB. There are two special cases: 1) the last 3 bits become 111, or 2) the last 4 bits become 1011. For these two cases, we need add 1 first, because the zeros generated by the carry-on will reduce the count overall.

        public int integerReplacement(int intN) 
        {
            int count = 0;
            long n = intN;
            while(n > 1)
            {
                if((n & 0x7) == 0x7 || (n & 0xB) == 0xB) n++;
                else
                {
                    if((n & 1) == 1) count++;
                    
                    n >>= 1;
                }            
                count++;
            }
            return count;
        }
    

  • 0
    A
    This post is deleted!

  • 0
    A
    This post is deleted!

Log in to reply
 

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