8ms, C++, using bit manipulation, log(n) time complexity


  • 0
    N
    class Solution {
    public:
        int mySqrt(int x) {
            if( x <= 0){
                return 0;
            }
            int temp = x;
            int no_bits = 0;
            while(temp >> no_bits){
                no_bits++;
            }
            no_bits = (no_bits+1)/2 - 1;
            int result = 1 << no_bits;
            
            while( (no_bits--) > 0){
                result += (1 << no_bits);
                if(x/result < result){
                    result -= (1 << no_bits);
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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