367. Valid Perfect Square

Description

The problem is to determine whether a given number num is a perfect square. A perfect square is an integer that is the square of an integer. For example, 16 is a perfect square because 4 × 4 = 16, but 20 is not a perfect square because there is no integer that squares to 20.

Intuition

A brute force approach would be to try every number from 1 to num and check if its square equals num. This approach can be inefficient for large numbers, so instead, we can limit the number of checks by iterating up to sqrt(num).

To avoid overflow issues (which exist in certain programming languages like C++), we handle the multiplication carefully. In languages like Python, there's no risk of overflow due to the dynamic nature of integer types.

Approach

1. Initialize a variable i starting from 1 and iterate until i*i exceeds num.
2. For each value of i, check if i*i equals num. If it does, return True as num is a perfect square.
3. If no such i is found where i*i == num, return False.
4. In some languages like C++, ensure that the variable i is of type long long to prevent overflow.

Complexity

Time Complexity:

O(√n)

• In the worst case, we loop until the square root of num.

Space Complexity:

O(1)

• Only a few extra variables are used, so the space complexity is constant.

Code

C++

class Solution {
public:
    bool isPerfectSquare(int num) {
        long long q = num / 4;  // Use long long to avoid overflow
        long long i = 1;        // Use long long for i as well
        while (i * i <= num) {  // Check if i*i exceeds num to avoid overflow
            if (i * i == num) {
                return true;
            } else {
                i++;
            }
        }
        return false;
    }
};

Python

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        q = num // 4  # Integer division in Python
        i = 1
        while i * i <= num:  # Check if i*i exceeds num
            if i * i == num:
                return True
            i += 1
        return False

Java

class Solution {
    public boolean isPerfectSquare(int num) {
        int q = num / 4;
        int i = 1;
        while (i <= q + 1) {
            if (i * i == num) {
                return true;
            } else {
                i++;
            }
        }
        return false;
    }
}

JavaScript

var isPerfectSquare = function (num) {
    let q = Math.floor(num / 4);
    let i = 1;
    while (i <= q + 1) {
        if (i * i == num) {
            return true;
        }
        else {
            i++;
        }
    }
    return false;
};