# A square number is 1+3+5+7+..., JAVA code

• ``````public boolean isPerfectSquare(int num) {
int i = 1;
while (num > 0) {
num -= i;
i += 2;
}
return num == 0;
}
``````

The time complexity is O(sqrt(n)), a more efficient one using binary search whose time complexity is O(log(n)):

``````public boolean isPerfectSquare(int num) {
int low = 1, high = num;
while (low <= high) {
long mid = (low + high) >>> 1;
if (mid * mid == num) {
return true;
} else if (mid * mid < num) {
low = (int) mid + 1;
} else {
high = (int) mid - 1;
}
}
return false;
}
``````

One thing to note is that we have to use long for mid to avoid mid*mid from overflow. Also, you can use long type for low and high to avoid type casting for mid from long to int.
And a third way is to use Newton Method to calculate the square root or num, refer to Newton Method for details.

``````public boolean isPerfectSquare(int num) {
long x = num;
while (x * x > num) {
x = (x + num / x) >> 1;
}
return x * x == num;
}
``````

• This post is deleted!

• 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)).

• This is a math problem：
1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9
36 = 1 + 3 + 5 + 7 + 9 + 11
....
so 1+3+...+(2n-1) = (2n-1 + 1)n/2 = nn

• complexity is sqrt n. Far slow than O(1) provided by dploop and log(n) from StefanPochmann

• Can someone explain me why I had a similar version, but just do addition, however, I got TLE:

``````public boolean isPerfectSquare(int num) {
int i = 1, temp = 1;
while(temp < num){
i += 2;
temp += i;
}
return temp == num;
}
``````

• If num is Integer.MAX_VALUE, you will got overflow.

• change the temp to a long, and you make it corrent

• Awesome! You guys rock!

• This post is deleted!

• This post is deleted!

• This is a math problem：
1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9
36 = 1 + 3 + 5 + 7 + 9 + 11
....
so 1+3+...+(2n-1) = (2n-1 + 1)n/2 = nn

:clap:

• @fhqplzj Very good solution. BTW, why is your reputation a negative number?

• @fhqplzj Nice idea, but it is n^0.5, worse than binary search logn.

• @iambright Hi iambright, could you explain more of why this is n^0.5? I thought it is O(n) cuz it need n/2 times check. Let me know if I'm wrong.

• @River3 1, 4, 9, 16, ... num = 1^2, 2^2, 3^2, 4^2, ..., num^0.5^2.

• great method，awesome

• actually O(log(n)) is more efficient then O(sqrt(n)) (it's obvious that n^2 is better than 2^n, the curve of sqrt(n) and log(n) is the opposite)

• Here is an alternative binary search solution for your reference. The invariant is sqrt(x) must be included in [l, r] and it holds:

1. Initialize: for any num >= 1, sqrt(num) must be in [1,num], so we add a check in the beginning.
2. Maintain: If num/m - m >= 0, we cannot ensure sqrt(x) is outside, eg 3*3<10. Otherwise, it's safe to shrink from right side. But if l == r-1, we set l=m which incurs dead loop. Therefore we ceiling m rather than floor.
3. Terminate: since we make progress in every case of the loop body even if l == r-1, the loop definitely terminates.

At last, we have l==r after the loop which means the square of l is closest to num. So we can know if num is valid perfect square by checking l*l == num.

``````    public boolean isPerfectSquare(int num) {
if (num <= 0) return false;
int l = 1, r = num;
while (l < r) {
int m = l + (r - l) / 2 + 1;
if (num / m >= m) l = m;
else r = m - 1;
}
return l * l == num;
}
``````

ps: Note that the difference between 69-Sqrt and 367-Valid Perfect Square problem.

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