Fast iterative c implementation. (0ms)


  • 0
    N

    Not as nice as recursion, but likely faster. Time was 0 ms, though that seems irrelevant,

    int integerReplacement(register int n) {
    	register int ret = 0;
            //handle overflow
    	if (n == INT_MAX) {
    		return sizeof(int)*8;
    	}
    
    	while (n != 1) {
    		if (n & 0x1) {
    			if (n == 3) {
    				ret += 2;
    				break;
    			}
    			n >>= 1;
    			if (n & 0x1) {
    				// add 1
    				n+=1;
    			}
    
    			while (n && (n & 0x1) == 0) {
    				n >>= 1;
    				ret++;
    			}
    			ret++;
    		} else {
    			n >>= 1;
    		}
    		ret++;
    	}
    	return ret;
    }
    

Log in to reply
 

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