O(sqrt(n/2)) Applying Fermat's theorm with Brahmagupta–Fibonacci identity

• First I check if number if perfect square, next I check if number fits Legendre's condition for 4 squares 4^a(8b+7) .
I check if number is prime and is prime I check that n%4==1. See https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares
If number is not a prime I check if the numbers it's composed of numbers that match Fermat's theorem.
By Brahmagupta–Fibonacci identity
https://en.wikipedia.org/wiki/Brahmagupta%E2%80%93Fibonacci_identity
if all factors(or subfactors) are prime and match condtion n%4==1 I am guaranteed that my number is sum of 2 squares. Otherwise it's sum of 3 squares by Legendre's theorem .

``````public class Solution {
public int numSquares(int n) {
if (Math.pow((int)Math.sqrt(n), 2) == n){
return 1;
}
while (n%4 == 0){
n = n/4;
}
if (n%8 == 7){
return 4;
}
if (n%2 == 0){
n = n/2; //OK to divide by 2. If N/2 has is sum of 2 squares so will be N.
}
if (isMod41PrimeOrSubP(n)){
return 2;
}
return 3;
}
private boolean isMod41PrimeOrSubP(int num) {
if (num%4 != 1){
return false;
}
for (int i=3; i*i<num; i=i+2){
if (num%i == 0) {
if (num%(i*i) == 0){
return isMod41PrimeOrSubP(num/(i*i));
}
return isMod41PrimeOrSubP(i)&&isMod41PrimeOrSubP(num/i);
}
}
return true;
}
}
``````

• Improved version

``````public int numSquares(int n) {
if (Math.pow((int)Math.sqrt(n), 2) == n){
return 1;
}
while (n%4 == 0){
n = n/4;
}
if (n%8 == 7){
return 4;
}
if (n%2 == 0){
n = n/2;
}
if (n%4 == 3){
return 3;
}
return helper(n, 3);
}
private int helper(int num, int start) {
int sq = (int)Math.sqrt(num);
for (int i=start; i<sq; i=i+4){
if (num%i == 0) {
int isq = i * i;
if (num%isq == 0){
return helper(num/isq, i);
}
return 3;
}
}
return 2;
}``````

• You only have one recursive call now. Do you still prefer the helper and recursion? I think a loop inside numSquares is a bit simpler:

``````public int numSquares(int n) {
...
...
int sq = (int)Math.sqrt(n);
for (int i=3; i<sq; i=i+4){
if (n%i == 0) {
int isq = i * i;
while (n%isq == 0)
n /= isq;
if (n%i == 0)
return 3;
sq = (int)Math.sqrt(n);
}
}
return 2;
}
``````

Updating `sq` as follows also seems to work, though I didn't fully think it through and I don't think it's an advantage:

``````public int numSquares(int n) {
...
...
int sq = (int)Math.sqrt(n);
for (int i=3; i<sq; i=i+4){
if (n%i == 0) {
int isq = i * i;
while (n%isq == 0) {
n /= isq;
sq /= i;
}
if (n%i == 0)
return 3;
}
}
return 2;
}``````

• I did try while loop. I know it sounds a little strange but recursive solution ended up being a little faster.

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