Problem

Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

Examples

Example 1:

Input: num = 16 Output: true Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

Example 2:

Input: num = 14 Output: false Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

Constraints

1 <= num <= 2^31 - 1

# Is Perfect Square

## Problem Description

Given a positive integer `num`, determine if it is a perfect square without using built-in square root functions.

A perfect square is an integer that can be expressed as the square of another integer. For instance, 16 is a perfect square because it's 4 * 4.

## Naive Solution

A brute-force approach would be to iterate from 1 to `num` and check if the square of any number equals `num`. This method is inefficient, especially for large numbers.

```python
def is_perfect_square_naive(num):
    if num < 1:
        return False
    for i in range(1, num + 1):
        if i * i == num:
            return True
        elif i * i > num:
            return False
    return False

Optimal Solution: Binary Search

A much more efficient solution involves using binary search. Since we know that the square root of num must lie between 1 and num/2 (or num if it's 1 or 0), we can apply binary search to find it.

def is_perfect_square(num):
    if num < 0:
        return False  # Negative numbers cannot be perfect squares
    if num <= 1:
        return True   # 0 and 1 are perfect squares

    left, right = 1, num
    while left <= right:
        mid = left + (right - left) // 2  # To prevent overflow
        square = mid * mid

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

    return False

Big(O) Run-time Analysis

The binary search algorithm has a time complexity of O(log n), where n is the input number num. This is because binary search halves the search space with each iteration.

Big(O) Space Usage Analysis

The space complexity of the binary search algorithm is O(1) because it uses a constant amount of extra space regardless of the input size. We only use a few variables (left, right, mid, square).

Edge Cases and Handling

1. Negative Numbers: Perfect squares cannot be negative. The code handles this by returning False if num < 0.
2. Zero and One: 0 and 1 are perfect squares. The code handles these by returning True if num <= 1.
3. Large Numbers: To prevent integer overflow when calculating the square of mid, it's crucial to use mid = left + (right - left) // 2 instead of (left + right) // 2.
4. Non-Integer Square Root: If num is not a perfect square, the binary search will narrow down the range until left > right, at which point the function returns False.