# Java Three Solutions 1,3,5,.. Sequence/Binary Search/Newton

1. a square number is 1+3+5+7+... Time Complexity O(sqrt(N)) (Credit to lizhibupt, thanks for correcting this).
2. binary search. Time Complexity O(logN)
3. Newton Method. See [this wiki page][1]. Time Complexity is close to constant, given a positive integer.
``````

public boolean isPerfectSquare(int num) {
if (num < 1) return false;
for (int i = 1; num > 0; i += 2)
num -= i;
return num == 0;
}

public boolean isPerfectSquare(int num) {
if (num < 1) return false;
long left = 1, right = num;// long type to avoid 2147483647 case

while (left <= right) {
long mid = left + (right - left) / 2;
long t = mid * mid;
if (t > num) {
right = mid - 1;
} else if (t < num) {
left = mid + 1;
} else {
return true;
}
}

return false;
}

boolean isPerfectSquare(int num) {
if (num < 1) return false;
long t = num / 2;
while (t * t > num) {
t = (t + num / t) / 2;
}
return t * t == num;
}

[1]: https://en.wikipedia.org/wiki/Newton%27s_method``````

• The time complexity of solution 1 should be O(sort(n)), not linear:

Let x be the number of iterations needed to solve the problem, and let Σ be the sum from i = 1 to x. Σ(1 + 2i) = n => x + 2Σi = n => x + 2(x(x+1)) = n => 2x^2 + 3x = n => x = [-3 +/- sqrt(9 + 8n)]/4 => you can see that n is in a square root term, so the complexity should be O(sqrt(n)).

• You are right, the complexity of solution 1 should be O(sqrt(n))

• Newton's method will fail if the input is 1.

• Your implementation of Newton's method will fail if the input is 1 because you divide the number by 2 initially.

Modified implementation which will work with all test cases:

``````public boolean isPerfectSquare_newton(int num) { // O(1)
// Newtons's method.
// Find square root of num and square it
// square == num ? true : false;

long t = num;
while (t * t > num) {
t = (t + num / t) / 2;
}
return t * t == num;
}``````

• num can be 0

• You are so clever.

• @kira4 Nop. The question states: "Given a positive integer num".

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.