Leetcode: Valid Perfect Square

Valid Perfect Square

Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/valid-perfect-square
## Basic Ideas: Binary search
##             Search in between [1^2, 2^2, 3^2, ... num^2]
##     But we have to use long for mid to avoid *mid\mid from overflow
## Complexity: Time O(log(n)), Space O(1)
class Solution(object):
    def isPerfectSquare(self, num):
        :type num: int
        :rtype: bool
        if num <= 0:
            return False
        left, right = 1, num
        while left<= right:
            mid = left + (right-left)/2
            v = mid*mid
            if v == num:
                return True
            elif v < num:
                left = mid + 1
                right = mid - 1
        return False

Share It, If You Like It.

Leave a Reply

Your email address will not be published.