# 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: