# 367. Valid Perfect Square
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.
# Solution
Approach 1: binary search for the square root -- O(logN)
time.
Approach 2: Newton's method -- running time unsure.
Approach 3: Use the trick that a perfect square number is the sum of odd numbers starting from 1 -- O(N)
time.
# Code (Python)
Approach 1:
class Solution(object):
# binary search for the squre root
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
left, right = 1, num
while left < right:
mid = (left + right) // 2
mid_squared = mid * mid
if mid_squared == num:
return True
elif mid_squared < num:
left = mid + 1
else:
right = mid - 1
return left * left == num
Approach 2:
# newton's method: https://math.mit.edu/~stevenj/18.335/newton-sqrt.pdf
def isPerfectSquare(self, num):
guess = num
while True:
if guess * guess == num:
return True
elif guess * guess > num:
next_guess = (guess + num / guess) // 2
guess = next_guess
# because the initial guess is always >= than num, we can stop when guess^2 < num
# otherwise the guess tend to oscillate between 2 consecutive integers
else:
return False
Approach 3:
# a perfect square number is the sum of odd numbers starting from 1:
# https://math.stackexchange.com/questions/639068/sum-of-odd-numbers-always-gives-a-perfect-square
def isPerfectSquare(self, num):
sum_of_odds = 1
next_num = 3
while sum_of_odds < num:
sum_of_odds += next_num
next_num += 2
return sum_of_odds == num
# Code (C++)
Approach 1:
Approach 2:
Approach 3: