Super simple one-loop solution. O(n) worst. O(log(n)) best.


  • 0
    G

    You want to minimize the number of 1-bits every step. You only need to look at the last two bits every step.
    Case 0b00 : Divide N by 2
    Case 0b10 : Divide N by 2
    Case 0b01 : Subtract 1, making the last two digits 0b00, reducing the number of 1s by one.
    Case 0b11 : Add 1, making the last two digits 0b00, reducing the number of 1s by at least two.

    N = 3 is a special case because the faster route is to subtract 1 and divide by 2. Logic above applies for all other integers.

    public class Solution {
        public int integerReplacement(int n) {
            long l_n = (long)n;
            int steps = 0;
            while (l_n != 1 && l_n != 3)
            {
                if ((l_n & 1) == 0)
                    l_n >>= 1;
                else if ((l_n & 3) == 3)
                    l_n += 1;
                else
                    l_n -= 1;
                steps++;
            }
            return l_n == 1 ? steps : steps + 2;
        }
    }
    

Log in to reply
 

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