[LeetCode] Perfect Squares

Well, after seeing the similar problems, you may have known how to solve this problem. Yeah, just to construct larger numbers from smaller numbers by adding perfect squares to them. This post shares a nice code and is rewritten below.

 1 class Solution {
 2 public:
 3     int numSquares(int n) {
 4         vector<int> dp(n + 1);
 5         iota(dp.begin(), dp.end(), 0);
 6         int ub = sqrt(n), next;
 7         for (int i = 0; i <= n; i++) {
 8             for (int j = 1; j <= ub; j++) {
 9                 next = i + j * j;
10                 if (next > n) break;
11                 dp[next] = min(dp[next], dp[i] + 1);
12             }
13         }
14         return dp[n];
15     }
16 };

Well, you may have noticed that the above code has many repeated computations. For example, for n = 10 and 11, we will recompute dp[0] to dp[10]. So a way to reduce the running time is to use static variables to store those results and return it if it has already been computed. Stefan posts severl nice solutions here.

Finally, the above strategy using static variables does not reduce the expected running time of the algorithm, which is still of O(n^(3/2)). And guess what? There exists a much faster O(n^(1/2)) algorithm using number theory, also posted by Stefan here. I rewrite its clear C solution in C++ below (well, just a copy -_-).

 1 class Solution {
 2 public:
 3     int numSquares(int n) {
 4         while (!(n % 4)) n /= 4;
 5         if (n % 8 == 7) return 4;
 6         for (int a = 0; a * a <= n; a++) {
 7             int b = sqrt(n - a * a);
 8             if (a * a + b * b == n)
 9                 return !!a + !!b;
10         }
11         return 3;
12     }
13 };