Two different solutions both accepted as best in C


  • 0

    Newton method


    int mySqrt(int x)
    {
        long g = x;
        while(g*g > x)
            g = (g + x/g) / 2;
        return g; 
    }
    

    Bit manipulation


    int mySqrt(int x)
    {
        if(x == 0 || x == 1)
            return x;
        int h = 0;
        while((long)(1 << h) * (long)(1 << h) <= x)
            h++;
        h--;
        int d = h - 1;
        int res = (1 << h);
        while(d >= 0)
        {
            if((long)(res | 1 << d)*(long)(res | 1 << d) <= x)
                res |= (1 << d);
            d--;
        }
        return res;
    }

Log in to reply
 

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