69. Sqrt(x)

Problem¶

Given a non-negative integer x, return the integer part of \(\sqrt{x}\).

Do not use exponentiation or built-in square root helpers.

Example:

x=8 -> r=2, because 2*2=4 <= 8 and 3*3=9 > 8

Key trick¶

Use binary search on the answer, not on the value itself.

Search the largest mid with mid * mid <= x.
This gives \(O(\log x)\) time.

Trap¶

The common mistakes are:

Returning the first mid that satisfies mid * mid <= x, instead of the largest one.
Using floating-point math, which can be imprecise.
Forgetting edge cases like x = 0 and x = 1.
Writing a brute-force loop, which is too slow for large x.

Why is it interesting?¶

It tests whether you can turn a math problem into a monotonic search problem.

The predicate mid * mid <= x is monotonic.
That makes binary search a natural interview solution.

Python solution¶

class Solution:
    def mySqrt(self, x: int) -> int:
        # We want the largest r such that r*r <= x.
        l, r = 0, x

        while l <= r:
            mid = (l + r) // 2
            square = mid * mid

            if square <= x:
                l = mid + 1
            else:
                r = mid - 1

        return r

Commented your solution¶

Your first solution is correct and idiomatic.

It uses binary search and has \(O(\log x)\) time.
return left - 1 is equivalent to returning right at the end.
The brute-force version is correct but too slow for interview constraints.

## Solution

# Works - in O(log(x))
class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        while left <= right:
            mid = (left + right) // 2
            if mid*mid <= x:
                left = mid + 1
            else:
                right = mid - 1
        return left - 1

Solution().mySqrt(8)

# Works - but brute force so slow
class Solution:
    def mySqrt(self, x: int) -> int:
        # we're looking for integer y such y*y <= x and (y+1)*(y+1) > x
        # - we can do it brut force
        # - or binary search
        y = 0
        while y*y <= x:
            y += 1
        return y - 1

Solution().mySqrt(8)