LeetCode 69: Sqrt(x)

Problem Restatement

We are given a non-negative integer x.

We need to return the square root of x rounded down to the nearest integer.

We cannot use built-in exponent functions or operators such as pow(x, 0.5) or x ** 0.5.

The official constraint is:

0 <= x <= 2**31 - 1

Input and Output

Function shape:

def mySqrt(x: int) -> int:
    ...

Examples

For:

x = 4

The square root is exactly 2, so the answer is:

2

For:

x = 8

The real square root is about:

2.828...

Rounded down, the answer is:

2

For:

x = 0

The answer is:

0

First Thought: Linear Search

The integer square root is the largest integer r such that:

r * r <= x

A direct approach is to try every number from 0 upward until the square becomes too large.

class Solution:
    def mySqrt(self, x: int) -> int:
        r = 0

        while (r + 1) * (r + 1) <= x:
            r += 1

        return r

This is correct, but it can be slow.

For large x, this loop may run many times.

Key Insight

The candidate answer is between 0 and x.

The function:

r * r

gets larger as r gets larger.

That gives us a monotonic condition:

r * r <= x

For small r, this condition is true.

For large r, this condition becomes false.

So we can binary search for the largest r where the condition is true.

Algorithm

Use binary search over possible answers.

Initialize:

left = 0
right = x
ans = 0

While left <= right:

1. Compute the middle value.
2. If mid * mid <= x, then mid is a valid candidate.
3. Store mid as the current answer and search to the right.
4. Otherwise, search to the left.

Return ans.

Correctness

The answer is the largest integer whose square is less than or equal to x.

During binary search, when mid * mid <= x, mid is a valid integer square root candidate. Since there may be a larger valid candidate, the algorithm records mid and moves the search range to the right.

When mid * mid > x, mid is too large. Every number larger than mid also has a square greater than x, so the algorithm safely discards the right side.

The search continues until every candidate has either been rejected or considered. The variable ans always stores the largest valid candidate seen so far. Therefore, after the search ends, ans is exactly the floor of the square root of x.

Complexity

Implementation

class Solution:
    def mySqrt(self, x: int) -> int:
        left = 0
        right = x
        ans = 0

        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid

            if square <= x:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1

        return ans

Code Explanation

Start with the full candidate range:

left = 0
right = x
ans = 0

Compute the middle safely:

mid = left + (right - left) // 2

Then square it:

square = mid * mid

If the square fits inside x, mid could be the answer:

if square <= x:
    ans = mid
    left = mid + 1

We move right because we want the largest valid value.

If the square is too large:

else:
    right = mid - 1

We move left.

At the end:

return ans

Overflow-Safe Variant

In Python, integers do not overflow.

In languages with fixed-size integers, mid * mid can overflow. A safer comparison is:

mid <= x // mid

That checks the same condition as mid * mid <= x, but avoids multiplication overflow.

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x

        left = 1
        right = x // 2
        ans = 1

        while left <= right:
            mid = left + (right - left) // 2

            if mid <= x // mid:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1

        return ans

Testing

def run_tests():
    s = Solution()

    assert s.mySqrt(0) == 0
    assert s.mySqrt(1) == 1
    assert s.mySqrt(4) == 2
    assert s.mySqrt(8) == 2
    assert s.mySqrt(9) == 3
    assert s.mySqrt(15) == 3
    assert s.mySqrt(16) == 4
    assert s.mySqrt(2147395599) == 46339
    assert s.mySqrt(2147483647) == 46340

    print("all tests passed")

run_tests()