# 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:

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | A non-negative integer `x` |
| Output | The integer part of `sqrt(x)` |
| Rounding | Round down |
| Restriction | Do not use built-in exponent functions |

Function shape:

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

## Examples

For:

```python
x = 4
```

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

```python
2
```

For:

```python
x = 8
```

The real square root is about:

```text
2.828...
```

Rounded down, the answer is:

```python
2
```

For:

```python
x = 0
```

The answer is:

```python
0
```

## First Thought: Linear Search

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

```python
r * r <= x
```

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

```python
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:

```python
r * r
```

gets larger as `r` gets larger.

That gives us a monotonic condition:

```python
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(log x)` | Binary search halves the candidate range each step |
| Space | `O(1)` | Only a few integer variables are stored |

## Implementation

```python
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:

```python
left = 0
right = x
ans = 0
```

Compute the middle safely:

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

Then square it:

```python
square = mid * mid
```

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

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

We move right because we want the largest valid value.

If the square is too large:

```python
else:
    right = mid - 1
```

We move left.

At the end:

```python
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:

```python
mid <= x // mid
```

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

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `0` | Smallest input |
| `1` | Smallest positive input |
| `4` | Perfect square |
| `8` | Rounds down |
| `9` | Perfect square |
| `15` | Just before a perfect square |
| `16` | Exact square after `15` |
| `2147395599` | Large non-square near 32-bit limit |
| `2147483647` | Maximum official input |