Description
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Examples:
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.Solution in Python
Key Insights:
- A perfect square is a number that can be written as k2 where k is an integer. For example, 1, 4, 9, 16, etc.
- We want to find the minimum number of perfect squares that sum up to the given number n. For instance:
- For n=12, the answer is 3 because 12=4+4+4.
- For n=13, the answer is 2 because 13=9+4.
Dynamic Programming Approach:
We can use dynamic programming to build a solution for this problem. The idea is to create a DP array dp where:
dp[i]represents the minimum number of perfect squares that sum up to i.
Steps:
- Base case:
dp[0] = 0because zero requires zero perfect squares.
- Transition/Recurrence:
- For each number i from 1 to n, we want to find the minimum number of perfect squares needed to sum up to i.
- For each perfect square k2 where k2≤i, we can update
dp[i]as: dp[i]=min(dp[i],dp[i−k2]+1) This means we are considering all the possible perfect squares k2 that can be subtracted from i and looking at the minimum number of perfect squares required for the remaining value i−k2.
- Final Answer:
- After filling up the DP array,
dp[n]will hold the least number of perfect squares that sum up to n.
- After filling up the DP array,
Python
import math
class Solution:
def numSquares(self, n: int) -> int:
# Create a DP array to store the minimum number of perfect squares for each number up to n.
dp = [float('inf')] * (n + 1) # Initialize dp array with a large number (infinity)
dp[0] = 0 # Base case: 0 requires 0 perfect squares
# Iterate over all numbers from 1 to n
for i in range(1, n + 1):
# Try all perfect squares less than or equal to i
for k in range(1, int(math.sqrt(i)) + 1):
square = k * k
dp[i] = min(dp[i], dp[i - square] + 1)
# The answer will be stored in dp[n], which is the minimum number of perfect squares that sum to n
return dp[n]Explanation of the Code:
- Initialization:
- We create a list
dpof size n+1, initialized with a large number (float('inf')). This represents the worst case where we haven’t yet computed the minimum number of perfect squares for each value. The valuedp[0]is set to 0, as no numbers are needed to sum to zero.
- We create a list
- Main Loop:
- We loop through each number i from 1 to n. For each i, we try subtracting every possible perfect square k2 that is less than or equal to i. We then update
dp[i]by considering the minimum value between its current value and the value dp[i−k2]+1 (which represents adding one perfect square to the solution of i−k2).
- We loop through each number i from 1 to n. For each i, we try subtracting every possible perfect square k2 that is less than or equal to i. We then update
- Final Answer:
- After processing all numbers from 1 to n, the value
dp[n]will give the least number of perfect squares that sum to n.
- After processing all numbers from 1 to n, the value
Solution in C++
C++
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits.h> // For INT_MAX
class Solution {
public:
int numSquares(int n) {
// Create a DP array to store the minimum number of perfect squares for each number up to n
std::vector<int> dp(n + 1, INT_MAX); // Initialize dp with a large number (INT_MAX)
dp[0] = 0; // Base case: 0 requires 0 perfect squares
// Iterate over all numbers from 1 to n
for (int i = 1; i <= n; ++i) {
// Try all perfect squares less than or equal to i
for (int k = 1; k * k <= i; ++k) {
int square = k * k;
dp[i] = std::min(dp[i], dp[i - square] + 1);
}
}
// Return the minimum number of perfect squares that sum to n
return dp[n];
}
};Solution in Javascript
JavaScript
var numSquares = function(n) {
// Create an array dp where dp[i] will represent the minimum number of perfect squares that sum to i
let dp = new Array(n + 1).fill(Infinity); // Initialize all values with Infinity (a large number)
dp[0] = 0; // Base case: 0 requires 0 perfect squares
// Loop through all numbers from 1 to n
for (let i = 1; i <= n; i++) {
// Try all perfect squares less than or equal to i
for (let k = 1; k * k <= i; k++) {
let square = k * k;
dp[i] = Math.min(dp[i], dp[i - square] + 1);
}
}
// The result is stored in dp[n], which represents the minimum number of perfect squares that sum to n
return dp[n];
};Solution in Java
Java
import java.util.Arrays;
class Solution {
public int numSquares(int n) {
// Create a DP array to store the minimum number of perfect squares for each number up to n
int[] dp = new int[n + 1];
// Initialize the dp array with a large value (we use Integer.MAX_VALUE as "infinity")
Arrays.fill(dp, Integer.MAX_VALUE);
// Base case: 0 requires 0 perfect squares
dp[0] = 0;
// Iterate over all numbers from 1 to n
for (int i = 1; i <= n; i++) {
// Try all perfect squares less than or equal to i
for (int k = 1; k * k <= i; k++) {
int square = k * k;
// Update dp[i] with the minimum count of perfect squares
dp[i] = Math.min(dp[i], dp[i - square] + 1);
}
}
// Return the minimum number of perfect squares that sum to n
return dp[n];
}
}