[3~8ms,sometimes beat 100%] Share my C++/C solution.


  • 0
    W

    Inspired by Fast inverse square root, O(1) time and space complexity.

    class Solution {
    public:
    	int mySqrt(int x) {
    	    if(x < 2) return x;
    		float y = x;
    		int i = *(int*)&y;
    		i = 0x1fbe7960 + (i >> 1);
    		long result = (int)(*(float*)&i);
    		result = (result + x / result) >> 1;
    		result = (result + x / result) >> 1;
    		return result * result > x ? result - 1 : result;
    	}
    };
    

    And for C is also 3~4ms

    int mySqrt(int x) {
        if(x < 2) return x;
    	float y = x;
    	int i = *(int*)&y;
    	i = 0x1fbe7960 + (i >> 1);
    	long result = (int)(*(float*)&i);
    	result = (result + x / result) >> 1;
    	result = (result + x / result) >> 1;
    	return result * result > x ? result - 1 : result;
    }
    

    I get the magic number 0x1fbe7960 by hand, but I cannot prove its accuracy. So I just test all the integers on my PC. The result proves the algorithm above is correct.
    I want to share my solution.

    The magic number 0x1fbe7960 is not too hard to memory since 0x1fbe7960 = 127 * 2^22 - 100000.


Log in to reply
 

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