Sqrt(x) — InterviewPrepKit

Problem

Given a non-negative integer x, compute the integer square root of x: the largest non-negative integer r such that r * r <= x. In other words, return the square root of x rounded down to the nearest integer.

You may not use any built-in exponent function or operator such as pow(x, 0.5) or x ** 0.5.

Examples

Input: x = 4 → Output: 2 (2 * 2 = 4 exactly.)
Input: x = 8 → Output: 2 (sqrt(8) ≈ 2.828…; rounding down gives 2, and indeed 2² = 4 ≤ 8 < 9 = 3².)
Input: x = 1 → Output: 1 (1 * 1 = 1 ≤ 1; edge values 0 and 1 are their own answers.)

Constraints

0 <= x <= 2^31 - 1
No built-in exponent/sqrt functions.
x up to ~2.1 billion means the answer can be up to 46340, and a solution should be logarithmic (or otherwise far better than trying every candidate).

Think about it first

Hint 1

You're looking for a number `r` with `r² <= x < (r+1)²`. As `r` grows, does `r² <= x` ever flip from False back to True?

Hint 2

The predicate `r² <= x` is True for all small `r` and False for all large `r` — a monotone boundary. You know an algorithm that finds such a boundary in O(log) steps without ever computing a square root.

Hint 3

Binary search `r` over `[0, x]`: if `mid² <= x`, `mid` is feasible — remember it and search higher; otherwise search lower. The last feasible `mid` is the answer. (Newton's iteration `r = (r + x // r) // 2` is the other classic route.)

TL;DR

Binary search for the largest r with r² <= x — O(log x) time, O(1) space (Newton’s method is the classic alternative).

Approach 1 — Brute force (count up)

Try r = 0, 1, 2, … until r² overshoots x; the previous r is the answer.

def mySqrt(x: int) -> int:
    r = 0
    while (r + 1) * (r + 1) <= x:
        r += 1
    return r

Time O(sqrt(x)) — up to ~46,340 iterations at x = 2^31 - 1. Space O(1). This passes at these limits, but the iteration count grows with the square root of the input, and the approach becomes impractical on 64-bit inputs. A logarithmic search is the right tool.

Approach 2 — Binary search on the answer

The predicate r² <= x is monotone: True for every r up to the true root, then False for all larger r. Finding the last True of a monotone predicate is exactly binary search, applied to the answer space [0, x] rather than to an array. We never compute a square root; we only square, which is allowed.

flowchart LR
    A["r = 0, 1, 2<br/>r² ≤ 8 → True"] --> B["answer = 2<br/>(boundary)"] --> C["r = 3, 4, ...<br/>r² > 8 → False"]

def mySqrt(x: int) -> int:
    lo, hi = 0, x
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            ans = mid          # feasible — remember it, try bigger
            lo = mid + 1
        else:
            hi = mid - 1       # too big — go smaller
    return ans

Walkthrough on x = 8:

lo=0, hi=8 → mid=4, 16 > 8 → hi=3.
lo=0, hi=3 → mid=1, 1 <= 8 → ans=1, lo=2.
lo=2, hi=3 → mid=2, 4 <= 8 → ans=2, lo=3.
lo=3, hi=3 → mid=3, 9 > 8 → hi=2.
lo > hi → return ans = 2.

Time O(log x) (~31 iterations worst case), space O(1).

Approach 3 — Newton’s method

We want the root of f(r) = r² − x. Newton’s method improves a guess by following the tangent line: r_next = r − f(r)/f'(r), which for square roots simplifies to r_next = (r + x/r) / 2. Run with integer division and started at or above the true root, the sequence decreases monotonically and stops exactly at the integer square root.

def mySqrt(x: int) -> int:
    if x < 2:
        return x
    r = x  # any start >= true sqrt works
    while r * r > x:
        r = (r + x // r) // 2
    return r

Walkthrough on x = 8:

r=8, 64 > 8 → r = (8 + 1) // 2 = 4.
r=4, 16 > 8 → r = (4 + 2) // 2 = 3.
r=3, 9 > 8 → r = (3 + 2) // 2 = 2.
r=2, 4 <= 8 → return 2.

Newton converges quadratically: the number of correct digits roughly doubles each step, so it takes about O(log log x) iterations in practice, typically fewer than binary search. Space O(1).

Common pitfalls

Rounding the wrong way: the answer for x = 8 is 2, not 3. If you binary-search a boundary, make sure you return the last r with r² <= x, not the first with r² > x.
Forgetting x = 0 and x = 1 — with hi = x and a careless loop these degenerate; the templates above handle them, but check yours.
In fixed-width languages, mid * mid overflows 32-bit ints (46341² > 2^31). Compare as mid <= x / mid or use 64-bit. Python integers are unbounded, but mention this in interviews.
Using x ** 0.5 and truncating: besides being banned, float precision can misround near perfect squares for large x (where sqrt lands on a value like ….9999999).

Pattern takeaway

This is binary search on the answer: no array in sight, just a monotone feasibility predicate (r² <= x) over a numeric range. Whenever a problem asks for “the largest value satisfying P” or “the smallest value satisfying P” and P flips exactly once as the value grows, binary-search the value itself and evaluate P at the midpoint.