Solution: Sqrt(x)

Statement

Given a non-negative integer x, compute and return the square root of x rounded down to the nearest integer. The result must also be non-negative.

Built-in exponent functions or operators (e.g., pow(x, 0.5) in C++ or x ** 0.5 in Python) are not permitted.

Constraints:

• $0 \leq$ x $\leq 2^{31} - 1$

Solution

The key insight is that the integer square root of x lies somewhere in the range $[1, x/2]$ ...