Naive Approach: Brute Force

A simple approach is to iterate through numbers from 1 up to num and check if the square of any of these numbers equals num. If we find such a number, then num is a perfect square; otherwise, it is not.

def is_perfect_square_brute_force(num):
    i = 1
    while i * i <= num:
        if i * i == num:
            return True
        i += 1
    return False

Time Complexity: O(√n), where n is the input number num.

Space Complexity: O(1), as we only use a constant amount of extra space.

Optimal Approach: Binary Search

Since we are looking for a specific value within a sorted range (1 to num), binary search is an efficient way to find the square root. We can apply binary search to find an integer x such that x*x == num. If we find such an x, then num is a perfect square. This avoids the need to iterate through every possible value up to the square root.

def is_perfect_square_binary_search(num):
    left, right = 1, num
    while left <= right:
        mid = left + (right - left) // 2
        square = mid * mid
        if square == num:
            return True
        elif square < num:
            left = mid + 1
        else:
            right = mid - 1
    return False

Time Complexity: O(log n), where n is the input number num.

Space Complexity: O(1), as we only use a constant amount of extra space.

Edge Cases:

• num = 1: Should return true since 1 * 1 = 1.
• num = 0: The problem states that 1 <= num <= 2^31 - 1, so num cannot be zero. However, for completeness, if zero were allowed, it should return true because 0 * 0 = 0.
• Large Numbers: The binary search approach handles large numbers efficiently due to its logarithmic time complexity. The multiplication mid * mid should not cause overflow, so using long may be necessary in languages like Java or C++ depending on the constraint for num, but not Python.

Summary

The binary search approach offers a significant improvement in time complexity compared to the brute-force method, making it the optimal solution for determining whether a number is a perfect square.