O(log(N)) Python solution


  • 0

    steps as below,

    1. if last digit of the number is not in 0,1,4,9,6,5, it is definitely not a perfect square.
    2. binary search the square root. If not exists, return False. Else return True.
    class Solution(object):
        def isPerfectSquare(self, num):
            last_digit = format(num)[-1]
            if last_digit not in ['0', '1', '4', '9', '6', '5']: return False
            j = num
            while (num / j) < j:
                j = j / 2
            i = j
            j = i * 2
            while i < j:
                m = (i + j) / 2
                k = num / m
                if (num % m == 0) and (k == m):
                    return True
                elif (m > k) and (not j == m):
                    j = m
                elif (m < k) and (not i == m):
                    i = m
                else:
                    return False
            return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.