3ms C solution, binary digit check combined with binary search


  • 0
    V

    If x has n binary digits, the square root of x contains m = floor((n + 1) / 2) digits, and then binary search among numbers of m digits. Speed seems to be stable at 3ms comparing with 3~6ms of pure binary search.

    int mySqrt(int x)
    {
        int d = binaryDigits(x);
        if (d == 0) return 0;
    
        d = (d + 1) / 2;
    
        int l = power(2, d - 1);
        int r = l * 2 - 1;
        int mid;
    
        while (l < r) {
            mid = (l + r) / 2;
            if (power(mid, 2) <= x)
                if (power(mid + 1, 2) > x)
                    return mid;
                else
                    l = mid + 1;
            else
                r = mid - 1;
        }
    
        return l;
    }
    
    int binaryDigits(int n)
    {
        int i = 0;
        for (; n > 0; n /= 2, i++);
        return i;
    }
    
    long power(int b, int p)
    {
        long i = 1;
        while (p-- > 0) i *= b;
        return i;
    }
    

Log in to reply
 

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