0ms O(1) space C++ solution with explanation


  • 0
    D

    The problem is how to perform the reduction steps on odd numbers.
    The trick is to maximize 0 at the end because dividing by 2 reduces the number faster than +/- by 1.
    If last bits are 11 --> +1, else if last bits are 01 --> -1.

    Exception: if the number is 3, reduce it by 1

    class Solution {
    public:
        int integerReplacement(int n_int) {
            int steps = 0;
            long n = n_int;
            while (n > 1) {
                if (n == 3) {
                    n--;
                } else {
                    if ((n & 0b11) == 0b11) {
                        n++;
                    } else if ((n & 0b11) == 0b01) {
                        n--;
                    } else {
                        n >>= 1;
                    }
                }
                ++steps;
            }
            return steps;
        }
    };
    

Log in to reply
 

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