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: TrueExample 2:
Input: 14 Returns: False
Analysis:
This problem is the same as the problem of leetcode 69: https://codebysteven.wordpress.com/2016/09/08/leetcode-69-sqrtx/
Basically we can just change the return value from double to be boolean.
Time complexity: O(logn)
Space complexity: O(1)
Below is the code:
public class Solution { public boolean isPerfectSquare(int num) { // O(logn) binary search // Corner case if (num == 0 || num == 1) { return true; } long start = 1; long end = num; while (start + 1 < end) { long mid = start + (end - start) / 2; if (mid * mid == num) { return true; } else if (mid * mid < num) { start = mid; } else { end = mid; } } return false; } }