Valid Perfect Square

Question

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

Tags

• Mathematics
• Binary Search

Thought

This problem is similar to the Sqrt(x) problem. Thus, we can use the same idea to check whether this is a perfect square number.

Code

class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        low, high = 0, num
        while low <= high:
            mid = (low + high) / 2
            if mid**2 == num:
                return True
            elif mid**2 > num:
                high = mid - 1
            else:
                low = mid + 1
        if low**2 != num and high**2 != num:
            return False
        else:
            return True