3.2 Calculating Square Root

69. Sqrt(x)

Problem Description

Given a non-negative integer x, calculate its square root and round it down to the nearest integer.

Input and Output Example

The input is an integer, and the output is also an integer.

Input: 8
Output: 2

The square root of 8 is 2.82842..., and rounding it down gives 2.

Solution Explanation

We can think of this problem as: given a non-negative integer x, find the solution to $f(t) = t^2 − x = 0$. Since we only consider $t ≥ 0$, $f(t)$ is monotonically increasing in its domain. Given that $f(0) = −x ≤ 0$ and $f(x) = x^2 − x ≥ 0$, we can use binary search on the interval $[0, x]$ to find the solution where $f(t) = 0$. Here, we adopt a left-closed, right-closed approach.

In the C++ solution, using $mid = (l + r) / 2$ might result in overflow due to $l + r$, so we use $mid = l + (r − l) / 2$ instead. Directly calculating $mid ∗ mid$ might also overflow, so we compare $mid$ with $x / mid$ instead.

C++

int mySqrt(int x) {
    int l = 1, r = x, mid, x_div_mid;
    while (l <= r) {
        mid = l + (r - l) / 2;
        x_div_mid = x / mid;
        if (mid == x_div_mid) {
            return mid;
        }
        if (mid < x_div_mid) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return r;
}

Python

def mySqrt(x: int) -> int:
    l, r = 1, x
    while l <= r:
        mid = (l + r) // 2
        mid_sqr = mid**2
        if mid_sqr == x:
            return mid
        if mid_sqr < x:
            l = mid + 1
        else:
            r = mid - 1
    return r

Additionally, this problem can be solved using a faster algorithm—Newton's Iterative Method. The formula is $t_{n+1} = t_n - \frac{f(t_n)}{f'(t_n)}$. For $f(t) = t^2 − x = 0$, the iteration formula becomes $t_{n+1} = \frac{t_n + \frac{x}{t_n}}{2}$.

C++

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

Python

def mySqrt(x: int) -> int:
    t = x
    while t**2 > x:
        t = (t + x // t) // 2
    return t