Newton's Method with Integer Math Only


  • 0
    H
    int mySqrt(int x) {
        if (x < 0) return 0;
        if (x < 2) return x;
        int x0 = x / 2 + 1, y, y0;
        while ((y = x0 / 2 + x / (2 * x0)) < x0) x0 = y;
        if (y * y == x) return y;
        else if (x0 * x0 == x) return x0;
        else if (x0 * x0 <= x - x0 - x0 - 1) return x0 + 1;
        else return x0;
    }

Log in to reply
 

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