Perfect Squares

Given a positive integer n , find the least number of perfect squares which sum to n

Example Test Cases

Sample Test Case 1

Input grid: 5
Expected Output: 2
Explanation: We need minimum two perfect squares to sum up to 5. for example, 5 can be written as
5 = 1² + 2²

Sample Test Case 2

Input grid: 12
Expected Output: 3
Explanation: You need minimum of three perfect squares to write 12:
12 = 2² + 2² + 2²

Solution

We can solve this problem by using recursion and then memoizing the results.
Let f(n) be the minimum number of perfect squares needed to form n .
Therefore, we can write f(n) = min(f(n - 1²), f(n - 2²), f(n - 3²), f(n - 4²),....f(n - i²)) + 1; for all i such that i² < n
Since, we might end up computing this function again and again for same numbers, we can memoize the results and store it in an array/map as shown below in the implementation.

Solution Implementation

#include <bits/stdc++.h>
using namespace std;

int solve(vector& answer, int sum) {
    int mi = INT_MAX;

    // If the answer[sum] is not computed, compute it.
    if (answer[sum] < 0) {
        for(int i = 1; i*i <= sum; i++) {
            mi = min(mi, solve(answer, sum - i*i) + 1);
        }
        answer[sum] = mi;
    }

    return answer[sum];
}

int main() {

    int n = 13;

    // answer[i] will store the minimum number of perfect squares needed to make i
    vector answer(n + 1);

    // if answer[i] is -1, it means that we have not computed answer[i] before.

    fill(answer.begin(), answer.end(), -1);

    // Since, the number of ways of forming 0 with perfect squares is 0
    answer[0] = 0;

    cout << "The minimum perfect squares needed are " << solve(answer, n) << "\n";
}