Given a positive integer num, write a function which returns True if num is a perfect square else False.
Follow up: Do not use any built-in library function such as sqrt
Example 1:
1
2
| Input: num = 16
Output: true
|
Example 2:
1
2
| Input: num = 14
Output: false
|
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public boolean isPerfectSquare(int num) {
return isPerfectSquareSearch(num);
}
public boolean isPerfectSquareNewTon(int num) {
if (num < 2) return true;
int root = num;
while (root - num / root > 0) {
root = (root + num/root) / 2;
System.out.printf("%d\n", root);
}
return root * root == num;
}
public boolean isPerfectSquareSearch(int num) {
if (num < 2) return true;
long left = 2, right = num / 2, x;
while (left <= right) {
x = left + (right - left) / 2;
if (x * x == num) return true;
if (x * x > num) {
right = x - 1;
} else {
left = x + 1;
}
System.out.printf("%d\n", x);
}
return false;
}
float abs(int num) {
if (num < 0)
return -num;
else
return num;
}
}
|