Sqrt(x)

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

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.

class Solution:
    def mySqrt(self, 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). That’s actually survivable here, but it scales as the square root of the input value, and the same idea dies instantly on 64-bit inputs; the problem is begging for a logarithmic search.

Approach 2 — Binary search on the answer

The insight: the predicate r² <= x is monotone — True for every r up to the true root, False forever after. Finding “the last True” of a monotone predicate is exactly binary search, applied to the answer space [0, x] rather than to an array. No square roots are ever computed; we only square, which is allowed.

class Solution:
    def mySqrt(self, 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:

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

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

Approach 3 — Newton’s method

The insight: we want the root of f(r) = r² − x. Newton’s method is the classical numerical algorithm that 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, starting at or above the true root, the sequence decreases monotonically and stops exactly at the integer square root.

class Solution:
    def mySqrt(self, 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:

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

Newton converges quadratically (the number of correct digits roughly doubles each step), so this takes O(log log x)-ish iterations in practice — typically faster 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 is immune but say it out loud in interviews.
• Using x ** 0.5 and truncating — besides being banned, float precision misrounds near perfect squares for large x (e.g. huge x where sqrt lands on ….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.