Sqrt(x) Solution | SkillFlow

Problem

Given a non-negative integer, find its integer square root — the largest integer whose square does not exceed the input. No floating-point math is needed; you only return the whole-number part.

Input: x = 8
Output: 2
Explanation: √8 ≈ 2.828, so we truncate to 2.

Counter-example: x = 9 → 3 (exact square root, no truncation).

Intuition

You're searching for the largest integer r such that r * r ≤ x. That's a classic binary search target: values below the answer satisfy the condition, values above don't — a monotone boundary. Instead of checking every integer from 0 to √x, you can halve the search space each step and find the answer in O(log x).

Approach 1 — Linear Scan

Step from 0 upward, advancing as long as the next integer still fits. Stop when squaring the next candidate would exceed x.

Start answer at 0.
Check whether (answer + 1)² is still ≤ x.
If yes, increment answer.
Repeat until the check fails, then return answer.

1def mySqrt(x: int) -> int:
2    answer = 0
3    while (answer + 1) * (answer + 1) <= x:
4        answer += 1
5    return answer

Time: O(√x) — we iterate roughly √x times before the condition fails.
Space: O(1) — only the running counter.

Approach 2 — Binary Search

Search in the range [0, x] for the largest integer whose square is ≤ x. Each iteration eliminates half the remaining candidates.

Initialize left = 0, right = x.
Compute mid = left + (right - left) / 2 to avoid overflow.
If mid * mid == x, return mid immediately.
If mid * mid < x, the answer is at least mid — move left = mid + 1.
If mid * mid > x, the answer is below mid — move right = mid - 1.
When the loop ends (left > right), right is the largest value confirmed to satisfy r * r ≤ x — return it.

1def mySqrt(x: int) -> int:
2    left, right = 0, x
3    while left <= right:
4        mid = left + (right - left) // 2
5        if mid * mid == x:
6            return mid
7        elif mid * mid < x:
8            left = mid + 1
9        else:
10            right = mid - 1
11    return right  # right is the floor of sqrt(x) when loop exits

Time: O(log x) — the search range halves each iteration.
Space: O(1) — only a few pointers.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(√x)	O(1)	Only for tiny inputs or when code simplicity is paramount
Binary Search	O(log x)	O(1)	General case — standard for any "find the boundary" problem

Common Mistakes

Integer overflow in mid * mid: During early iterations, mid can be close to x itself (up to ~2 billion for max input). As an int, mid * mid overflows before the search narrows. Declare mid as long in Java or long long in C++; Python handles big integers natively.
Returning left instead of right after the loop: When binary search exits with left > right, it's right that holds the last index confirmed to satisfy r * r ≤ x. Returning left yields a value one too high for every non-perfect-square input.
Unsafe bounds when starting right = x / 2: Setting right = x / 2 is a valid optimization since √x ≤ x / 2 for x ≥ 4, but it breaks for x = 0 and x = 1 where x / 2 = 0, making the answer 1 unreachable. Either start right = x or add an early return for x < 2.
Overflow in the linear scan's condition: Writing i * i <= x in Java/C++ overflows once i exceeds ~46341 on a 32-bit int. Use i <= x / i to avoid squaring, or cast to long/long long as shown above.
Returning ceiling instead of floor: It's easy to flip the binary search direction and accidentally return the smallest integer whose square is ≥ x. The floor requires keeping right = mid - 1 when too high, and returning right — double-check the invariant against the example x = 8 → 2, not 3.

Sqrt(x) — Solution