# 279-perfect-squares

## Question

https://leetcode.com/problems/perfect-squares/description/

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

Example:

``````Given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
``````

## Thought Process

1. DP
1. Use array of n + 1 to store the count
2. Every time the, we try to see the best solution by checking all the i - j * j count, where i is the current element and j range to 1 until sqrt(i)
3. Time complexity O(n^1.5)
4. Space complexity O(n)
2. Math
1. Base on [Lagrange's four-square theorem]([https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem](https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem)\), the answer is limit by 4
2. The number representation can be found here, http://www.alpertron.com.ar/4SQUARES.HTM
3. Perfect squares has one factor
4. If the representation is 4^k*(8*m + 7), there are 4 factors
5. If the n - perfectSquare is also a perfect square, then there are two factors
6. Otherwise there are 3 factors
7. Time complexity O(1)
8. Space complexity O1)

## Solution

``````class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = i;
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
``````
``````class Solution {
public int numSquares(int n) {
if (isPerfectSquare(n)) return 1;
while (n % 4 == 0) n /= 4;
if (n % 8 == 7) return 4;
for (int i = 1; i * i <= n; i++) {
if (isPerfectSquare(n - i * i)) return 2;
}
return 3;
}

private boolean isPerfectSquare(int i) {
int a = (int) Math.sqrt(i);
return a * a == i;
}
}
``````