367. Valid Perfect Square - Explanation

Problem Link

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

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(n)O(\sqrt {n})
  • Space complexity: O(1)O(1)

2. In-Built Function

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

Time & Space Complexity

  • Time complexity: O(1)O(1)
  • Space complexity: O(1)O(1)
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)O(\log n)
  • Space complexity: O(1)O(1)

4. Math

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(n)O(\sqrt {n})
  • Space complexity: O(1)O(1)

5. Newton's Method

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)O(\log n)
  • Space complexity: O(1)O(1)

6. Bit Manipulation

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)O(1) since we iterate at most 1515 times.
  • Space complexity: O(1)O(1)