Sqrt(x)

How it works

Newton's method is a numerical technique for finding roots of equations. To find sqrt(x), we solve r^2 = x, or equivalently find the root of f(r) = r^2 - x. Newton's iteration formula gives us r_new = (r + x/r) / 2. Starting with an initial guess of x, we repeatedly apply this formula until r^2 <= x, which converges quickly to the answer.

Steps

1. Initialize r = x as the starting guess.
2. While r * r > x, update r = (r + x / r) / 2 (using integer division, or right shift by 1).
3. The loop converges when r^2 <= x.
4. Return r as the integer square root.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Integer Overflow When Squaring

When computing m * m during binary search, the result can overflow if m is large (e.g., close to 46340 for 32-bit integers). Always cast to a 64-bit type before multiplication, such as (long)m * m in Java or (long long)m * m in C++, to prevent incorrect comparisons.

Off-by-One Errors in Binary Search

A subtle mistake is returning m when m * m < x instead of tracking it as a candidate and continuing to search for a larger valid value. The correct approach is to store m in a result variable when m * m <= x and keep searching, returning the stored result when the loop ends.

class Solution:
    def mySqrt(self, x: int) -> int:
        r = x
        while r * r > x:
            r = (r + x // r) >> 1
        return r

class Solution {
public:
    int mySqrt(int x) {
        long long r = x;
        while (r * r > x) {
            r = (r + x / r) >> 1;
        }
        return r;
    }
};