c++ 0 ms very simple solution


  • 0
    M

    The key idea comes from looking at the binary representation. If the number is even, we always get rid of one digit. When it's odd, we need to decide, whether to subtract one or add one. That depends on how many 'ones' we get rid of in either case. if there are 2 'ones' (11) then by adding one we get rid of both of them, while subtracting one helps to eliminate last one only. Solution: if the number is even, divide, if it's odd, check last 2 bits and decide on +1 or -1.

    class Solution {
    public:
        int integerReplacement(int n) {
            int count = 0;
            long l = n; //to avoid overflow
            while(l > 1){
                if (l & 1) {
                    l += (l & 3) == 3 && l != 3 ? 1 : -1;
                } else {
                    l >> 1;
                }
                count++;
            }
            return count;
        }
    };
    

Log in to reply
 

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