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;
}
};
4ms C++ Solution Without DP or BFS


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 nonnegative 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 nonnegative integers k and t, then p^(2t+2)n ).