# LeetCode 367: Valid Perfect Square

## Problem Restatement

Given a positive integer `num`, return `True` if it is a perfect square.

A perfect square is an integer that can be written as:

```python
x * x
```

where `x` is also an integer.

We must not use built-in square root functions such as `sqrt`. The constraint is `1 <= num <= 2^31 - 1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Positive integer `num` |
| Output | `True` if `num` is a perfect square, otherwise `False` |
| Restriction | Do not use built-in square root functions |

Example function shape:

```python
def isPerfectSquare(num: int) -> bool:
    ...
```

## Examples

Example 1:

```python
num = 16
```

Since:

```python
4 * 4 = 16
```

the answer is:

```python
True
```

Example 2:

```python
num = 14
```

There is no integer `x` such that:

```python
x * x == 14
```

because:

```python
3 * 3 = 9
4 * 4 = 16
```

So the answer is:

```python
False
```

## First Thought: Linear Search

The simplest method is to try every integer from `1` upward.

```python
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        x = 1

        while x * x <= num:
            if x * x == num:
                return True
            x += 1

        return False
```

This works, but it may check many numbers.

For large `num`, the loop may run around:

```python
sqrt(num)
```

times.

We can do better with binary search.

## Key Insight

If `x * x` is too small, then every smaller number also has a square that is too small.

If `x * x` is too large, then every larger number also has a square that is too large.

So the predicate has an ordered structure.

That means we can binary search over possible values of `x`.

The square root of `num` must be between:

```python
1
```

and:

```python
num
```

inclusive.

## Algorithm

Use binary search on the integer range `[1, num]`.

At each step:

1. Compute the middle value.
2. Compute `middle * middle`.
3. If it equals `num`, return `True`.
4. If it is smaller than `num`, search the right half.
5. If it is larger than `num`, search the left half.
6. If the search ends without equality, return `False`.

## Correctness

The search range always contains every possible integer square root that has not been ruled out.

When `mid * mid < num`, `mid` and every smaller value cannot be the square root, so the algorithm safely moves `left` to `mid + 1`.

When `mid * mid > num`, `mid` and every larger value cannot be the square root, so the algorithm safely moves `right` to `mid - 1`.

When `mid * mid == num`, an integer square root has been found, so `num` is a perfect square.

If the loop ends, every possible integer candidate has been ruled out. Therefore, `num` is not a perfect square.

## Complexity

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

## Implementation

```python
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left = 1
        right = num

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

            if square == num:
                return True

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

        return False
```

## Code Explanation

The search begins with all possible roots:

```python
left = 1
right = num
```

The midpoint is computed this way:

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

In Python, overflow is not a problem. In languages with fixed-width integers, this form is safer than `(left + right) // 2`.

Then we compute:

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

If it matches `num`, we found the integer square root.

If the square is too small:

```python
left = mid + 1
```

If the square is too large:

```python
right = mid - 1
```

If no exact square is found, return:

```python
False
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isPerfectSquare(1) is True
    assert s.isPerfectSquare(4) is True
    assert s.isPerfectSquare(9) is True
    assert s.isPerfectSquare(14) is False
    assert s.isPerfectSquare(16) is True
    assert s.isPerfectSquare(808201) is True
    assert s.isPerfectSquare(2147483647) is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `1` | Smallest valid input |
| `4`, `9`, `16` | Basic perfect squares |
| `14` | Between two perfect squares |
| `808201` | Larger perfect square |
| `2147483647` | Upper constraint area |