367. Valid Perfect Square - Explanation

Description

You are 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.

Example 1:

Input: num = 16

Output: true

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

Example 2:

Input: n = 15

Output: false

Explanation: We return false because square root of 15 is not an integer.

Constraints:
1 <= n <= ((2^31) - 1)

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The most straightforward approach is to try every integer starting from 1 and check if its square equals the input number. We keep incrementing until either we find a match (perfect square) or the square exceeds the input (not a perfect square). Since we only need to check up to the square root of the number, this terminates reasonably quickly.

Algorithm

Start with i = 1.
Compute sq = i * i.
If sq > num, the number is not a perfect square. Return false.
If sq == num, we found the square root. Return true.
Increment i and repeat.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        for i in range(1, num + 1):
            sq = i * i
            if sq > num:
                return False
            if sq == num:
                return True

Time & Space Complexity

Time complexity: $O(\sqrt {n})$
Space complexity: $O(1)$

2. In-Built Function

Intuition

Most programming languages provide a built-in square root function. We can use it to compute the square root, truncate it to an integer, and then verify by squaring it back. If the squared result equals the original number, it is a perfect square. This leverages optimized library implementations for a quick solution.

Algorithm

Compute the integer square root: sqRoot = floor(sqrt(num)).
Check if sqRoot * sqRoot == num.
Return true if they are equal, false otherwise.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        sqRoot = int(sqrt(num))
        return sqRoot * sqRoot == num

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

3. Binary Search

Intuition

Instead of checking every number sequentially, we can use binary search to find the square root more efficiently. The search space is from 1 to num. For each midpoint, we compute its square: if it is too large, search the left half; if too small, search the right half; if equal, we found a perfect square. This reduces the number of checks from O(sqrt(n)) to O(log n).

Algorithm

Initialize l = 1 and r = num.
While l <= r:
- Compute the midpoint m = l + (r - l) / 2.
- Compute sq = m * m.
- If sq > num, search left: r = m - 1.
- If sq < num, search right: l = m + 1.
- If sq == num, return true.
If the loop ends without finding a match, return false.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        l, r = 1, num

        while l <= r:
            m = l + (r - l) // 2
            sq = m * m
            if sq > num:
                r = m - 1
            elif sq < num:
                l = m + 1
            else:
                return True

        return False

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Math

Intuition

There is a beautiful mathematical property: perfect squares can be expressed as the sum of consecutive odd numbers. For example, 1 = 1, 4 = 1+3, 9 = 1+3+5, 16 = 1+3+5+7, and so on. We can repeatedly subtract consecutive odd numbers from the input. If we eventually reach exactly zero, the number is a perfect square.

Algorithm

Initialize i = 1 (the first odd number).
While num > 0:
- Subtract i from num.
- Increment i by 2 to get the next odd number.
If num == 0, the original number was a perfect square. Return true.
Otherwise, return false.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        i = 1
        while num > 0:
            num -= i
            i += 2
        return num == 0

Time & Space Complexity

Time complexity: $O(\sqrt {n})$
Space complexity: $O(1)$

5. Newton's Method

Intuition

Newton's method is a fast iterative technique for finding roots of equations. To find the square root of num, we want to solve x^2 = num, or equivalently find the root of f(x) = x^2 - num. Newton's method gives us the iteration formula: x_new = (x + num/x) / 2. Starting from an initial guess (the number itself), each iteration brings us closer to the actual square root. Once converged, we check if the result squared equals the input.

Algorithm

Initialize r = num as the initial guess.
While r * r > num:
- Update r = (r + num / r) / 2.
After convergence, check if r * r == num.
Return true if equal, false otherwise.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        r = num
        while r * r > num:
            r = (r + (num // r)) // 2
        return r * r == num

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

6. Bit Manipulation

Intuition

We can construct the square root bit by bit, from the most significant bit to the least significant. For a 32-bit integer, the square root fits in at most 16 bits. We try setting each bit position and check if the resulting number squared is still within bounds. If setting a bit makes the square too large, we clear that bit; otherwise, we keep it. This builds the largest integer whose square does not exceed the input.

Algorithm

Initialize r = 0 and mask = 1 << 15 (starting from the highest possible bit).
While mask > 0:
- Set the current bit: r |= mask.
- If r > num / r (meaning r^2 would exceed num), clear the bit: r ^= mask.
- Shift the mask right: mask >>= 1.
After processing all bits, check if r * r == num.
Return true if equal, false otherwise.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        r, mask = 0, 1 << 15

        while mask > 0:
            r |= mask
            if r > (num // r):
                r ^= mask
            mask >>= 1

        return r * r == num

Time & Space Complexity

Time complexity: $O(1)$ since we iterate at most $15$ times.
Space complexity: $O(1)$

Common Pitfalls

Integer Overflow When Squaring

When computing m * m in binary search or brute force approaches, the result can overflow if using 32-bit integers. For example, if m = 46341, then m * m = 2147488281 which exceeds the maximum 32-bit signed integer. Always use long or long long for the squared value, or use division (m > num / m) to avoid overflow.

Floating-Point Precision Issues

When using the built-in sqrt() function, floating-point precision can cause incorrect results. For example, sqrt(2147395600) might return 46339.999989... which truncates to 46339 instead of 46340. Always verify by squaring the integer result and comparing with the original number, rather than relying solely on the floating-point square root.