367. Valid Perfect Square

Description

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

Solution

很有意思的一道题。最开始的想法是从1开始计算平方，直到遇到num为止。可以AC，但是还有更巧妙的解法。

Math, time O(sqrt(n)), space O(1)

利用数学规律：a square number is 1+3+5+7+…

class Solution {
    public boolean isPerfectSquare(int num) {
        int i = 1;

        while (num > 0) {
            num -= i;
            i += 2;
        }
        
        return num == 0;
    }
}

Binary Search, time O(logN), space O(1)

sqrt(num)当然在1到num之间，用二分找。注意用long来避免overflow。

class Solution {
    public boolean isPerfectSquare(int num) {
        int low = 1;
        int high = num;
        
        while (low <= high) {
            long mid = (low + high) >>> 1;  // unsigned bit operation
            
            if (mid * mid == num) {
                return true;
            } else if (mid * mid < num) {
                low = (int) mid + 1;
            } else {
                high = (int) mid - 1;
            }
        }
        
        return false;
    }
}