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

Two ways to solve this:

1. Binary Search - to find the sqrt of this number, if not found: false, else: true
2. Math - a perfect square = 1+3+5+7+….2*i+1 (i>=0)

Binary Search

Note that the result of mid*mid should be long type, or else the product may exceed the integer boundary.

class Solution {
    public boolean isPerfectSquare(int num) {
        if(num==1) return true;
        else if(num<4) return false;
        long m=1, n=num;
        while(m<=n){
            long i=m+(n-m)/2;
            if(i*i==num) return true;
            else if(i*i<num) m=i+1;
            else n=i-1;
        }
        return false;
    }
}

Math Property

``` java
class Solution {
public boolean isPerfectSquare(int num) {
int ans = 1;
while(num>0){
num-=ans;
ans+=2;
}
return num==0;
}
}