# Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

## 方法一

• 一个平方数 if and only if each prime factor occurs to an even power in the number’s prime factorization.
• 两个平方数之和 if and only if each prime factor that’s 3 modulo 4 occurs to an even power in the number’s prime factorization.
• 三个平方数之和 if and only if it’s not of the form 4a(8b+7) with integers a and b.
• 四个平方数之和. Period. No condition. You never need more than four.
``````public class Solution {
public int numSquares(int n) {
int m = n;
while (m % 4 == 0)
m /= 4;
if (m % 8 == 7)
return 4;
for (int a = 0; a * a < (n / 2 + 1); a++) {
int b = (int) Math.sqrt(n - a * a);
if (a * a + b * b == n) {
return 1 + ((a == 0) ? 0 : 1);
}
}
return 3;
}
}
``````

## 方法二

According to the How to solve DP problems during Interview, it satisfied both conditions:

• Minimum
• Cannot sort / swap

Which means it can be solve by Dynamic Programming, and belongs to the One Sequence

DP Function: dp[x + y * y] = min(dp[x + y * y], dp[x] + 1)

Time Complexity: O(n * sqrt n)

``````public class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp = 0;
for (int i = 0; i <= n; i++) {
for (int j = 1; i + j * j <= n; j++) {
dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j]);
}
}
return dp[n];
}
}
``````