# Java solution O(n^1/2) time and O(1) space

• public class Solution {

``````    public int numSquares(int n) {
int m = n;
while( m % 4 == 0 )
m = m>>2;
if(m % 8 == 7)
return 4;

int sqrtOfn = (int) Math.sqrt(n);
if(sqrtOfn * sqrtOfn == n)//Is it a Perfect square?
return 1;
else{
for(int i = 1; i <= sqrtOfn; ++i){
int remainder = n - i*i;
int sqrtOfNum = (int) Math.sqrt(remainder);
if(sqrtOfNum * sqrtOfNum == remainder)
return 2;
}
}
return 3;
}
}``````

• This looks very efficient. Can you please explain the first steps of the algorithm?

• https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem
You may refer to 'Historical development' part.

• Thanks for the nice code and links :-)

• This post is deleted!

• Can someone explain why 4a(8b+7) guarantees that n is representable by not less than four squares? The wikipedia article just says that such number is not representable by three squares, but it doesn't say anything about one or two squares. Why such number can't be represented by sum of one or two squares?

Thanks!

• You may refer to Jacobi's four-square theorem.

• I didn't realize that if number is expressible by one or two squares it is also expressible by three squares. Additional squares can be trivially added by using 02.

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