Tricky Solution with comments


  • 0
    L

    There two cases as add one or minus one when n is odd. I found a add one rule that is adding one can make the next (high) bit 1 change to zero. For example, in a extreme case

    11111 (+1) 100000 (/2) 10000 (/2) 1000 (/2) 100 (/2) 10 (/2) 1
    6 times

    11111 (-1) 11110 (/2) 1111 (-1) 1110 (/2) 111 ...
    8 times

    a special case is n = 3
    11 (+1) 100 (/2) 10 (/2) 1
    3 times

    but

    11 (-1) 10 (/2) 1
    2 times

    class Solution {
    public:
        int integerReplacement(int n) {
    	if (n == INT_MAX) { // a special case
    	    return 32;
    	}
    
        	int cnt = 0;
        	while (n != 1) {
                if (n & 1) {
                    // a special case
                    if (n == 3) { // 11 -> 10 -> 1 not 11 -> 100 -> 10 -> 1
                        cnt += 2;
        		    return cnt;
        		}
    	        // [1] = 1 -> +
    	        // [1] = 0 -> -
    	        if (0x02 & n) { // add one will change 111 -> 1000
    	            ++n;
    	        } else {
                        // for example as n = 10001 just change to 10000 (minus one)
    	            --n;
    	        }
    	    } else {
    	        n >>= 1;
    	    }
                ++cnt;
        	}
            
            return cnt;
        }
    };

Log in to reply
 

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