Given a positive integer num, return true if num is a perfect square or false otherwise.
A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.
You must not use any built-in library function, such as sqrt.
Example 1:
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
Example 2:
Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.
Constraints:
- 1 <= num <= 231 - 1
My Solution
We can solve this problem with binary search. We need to use the integer type long for the start, end and mid pointers because looking at the constraints, the numbers we check could be very large. We start with the start pointer equal to 1 and the end pointer equal to the number. Then at every iteration we find the midpoint, check whether the midpoint squared is equal to the number and if it is we return true. If not, we update start end end accordingly. Finally if we exit the loop, we know that it is not a perfect square so we just return false.
Time complexity would be O(log n) due to binary search. Space complexity would be O(1) since we only use constant extra space.
class Solution {
public boolean isPerfectSquare(int num) {
long start = 1;
long end = num;
while (start <= end) {
long mid = start + (end-start)/2;
if (mid*mid == num) {
return true;
}
else if (mid*mid > num) {
end = mid-1;
}
else {
start = mid+1;
}
}
return false;
}
}