# 4ms C++ Solution Without DP or BFS

• ``````class Solution {
public:
int numSquares(int n) {
while (n % 4 == 0)    n /= 4;
if (n % 8 == 7)    return 4;
int m = sqrt(n);
if (m * m == n)    return 1;
if (n % 2 == 0)    n >>= 1;
if (n % 4 == 3)    return 3;
for (int i = 3; i * i < n; i += 4)
if (n % i == 0) {
bool odd = true;
n /= i;
while (n % i == 0) {
odd = !odd;
n /= i;
}
if (odd)    return 3;
}
return 2;
}
};``````

• How does this solution work?

• can you explain this solution?

• As we know, each positive integer n could be decomposed as sum of 4 squared numbers. Moreover, n could be decomposed as sum of 3 squared numbers if and only if n is not of form 4^t*(8k+7) for some non-negative integers k and t. Also, a sufficient and necessary condition for a positive integer n being decomposable to sum of two squared numbers is that each prime factor of n of form 4k+3 should have an even degree (i.e. if a prime p=4k+3 and p^(2t+1)|n for some non-negative integers k and t, then p^(2t+2)|n ).

• this seems to be a math solution instead of computer science solution. I guess interviewer wouldn't want to see such a solution during an interview, though it's really amazing.

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