Sqrt(x)
Sqrtx: given a non-negative integer x, return the integer part of its square root — the largest integer k such that k * k <= x.
- 0 <= x <= 2³¹ - 1
Intuition
Sqrt x asks for the integer part of a number's square root — the largest k with k² ≤ x. The built-in square root is off-limits, and floating-point results are unsafe anyway near large values, where rounding can land one off the true answer.
The structure to exploit is that k² increases monotonically with k. So a single guess is informative: if mid² ≤ x, then mid is a valid candidate and every smaller value is too, while if mid² > x, then mid and everything above it are ruled out.
Monotone comparisons are exactly the precondition for binary search, applied here to the answer rather than to any array:
- Binary search the candidates 0 through x, keeping the largest mid whose square does not exceed x.
The pattern is the same one behind Nth Root of Integer and the search-on-the-answer family generally.
One detail decides correctness in fixed-width languages: mid * mid can overflow long before it approaches x. With x near 2³¹, an early mid squares past the 32-bit limit and the comparison silently reads a wrapped value. Comparing mid against x / mid instead avoids the multiplication entirely, or use a 64-bit type.
Because the answer is a floor, the loop must remember the last valid candidate rather than expecting an exact hit — most inputs are not perfect squares.
Any time you need to find the boundary value of a monotonic function — 'the largest k such that f(k) <= target' — binary search on the answer is the tool. Here f(k) = k², but the same template works for cube roots, finding a threshold in a sorted array, or minimising a cost function that is convex.
Approach
Before reading on: price up what the direct approach costs here, then ask what pattern in the numbers removes the loop entirely. Aim for O(log x) time and O(1) space.
Search the answer range
The result lies between 0 and x. Set lo = 0 and hi = x, then binary search. There is no array here — the thing being halved is the range of candidate roots, the same shape as Nth Root of Integer.
Compare the square against x
For a guess mid, if mid * mid <= x then mid is a valid candidate — record it and search higher with lo = mid + 1. If the square exceeds x, search lower with hi = mid - 1.
Record the candidate rather than expecting a hit
The answer is a floor, and most inputs are not perfect squares, so the loop must save each valid mid rather than waiting for an exact match. The last saved value is the result.
Avoid the overflow
mid * mid overflows a 32-bit integer well before mid approaches large values of x. Compare mid <= x / mid instead, or use a 64-bit type — this is the usual cause of a wrong answer on the boundary tests.
Handle the trivial inputs
x of 0 or 1 returns itself. Handling them up front avoids reasoning about whether the general loop behaves correctly on a degenerate range.
Cost of the search
The range halves each iteration, giving O(log x) time and O(1) space. Newton's method converges faster in practice and is worth mentioning as the alternative, though binary search is easier to argue correct.
Solution & live demo
Common pitfalls
Using mid * mid == x as the only success condition
if mid * mid == x:
return midif mid * mid <= x:
ans = mid
left = mid + 1You need the floor of the square root, not an exact match. For non-perfect squares like x = 8, no mid satisfies mid² == 8, and the function would return nothing. Recording every mid where mid² <= x and continuing the search finds the correct floor.
Setting right = x // 2 to optimise the range
right = x // 2
right = x
For x = 1, x // 2 = 0, and the answer 1 is outside the range. The saving is negligible (one fewer iteration of log x) and breaks the smallest input.
Integer overflow when computing mid * mid in typed languages
int sq = mid * mid;
long sq = (long) mid * mid;
In Java/C++, mid can be up to ~46340 before mid **mid overflows a 32-bit int. For x near INT_MAX, mid is around 46340, and mid** mid exceeds 2^31. Python has arbitrary-precision ints so this doesn't apply there, but the C++ and Java solutions must use long.
Edge cases
x = 0The range is [0, 0]. mid = 0, 0 * 0 = 0 <= 0, so the answer is 0.
x = 1mid = 0 first, then left = 1, mid = 1, 1 <= 1, answer is 1.
x = 16mid = 4 gives 16 <= 16, so the answer is exactly 4. No truncation.