Skip to content

367. Valid Perfect Square

Math Binary Search

Problem - Valid Perfect Square

Easy

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: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

 

Constraints:

  • 1 <= num <= 231 - 1

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        # left = bisect_left(range(1, num + 1), num, key=lambda x: x * x) + 1
        # return left * left == num

        left = 0
        right = num

        while left <= right:
            mid = (left + right) // 2
            temp = mid * mid
            if num == temp:
                return True
            elif temp < num:
                left = mid + 1
            else:
                right = mid - 1

        return False

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 17.6 MB (96.27%)