# 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.
Approach 1: binary search for the square root --
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 --
# Code (Python)
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
# 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
# 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++)