Algorithm
Problem Name: 279. Perfect Squares
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.
Example 1:
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.
Constraints:
1 <= n <= 104
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int numSquares(int n) {
int i, j, k;
int *dp;
dp = malloc((n + 1) * sizeof(int));
//assert(dp);
dp[0] = 0;
for (i = 1; i < = n; i ++) {
k = dp[i - 1] + 1; // answer of preceeding number plus 1
j = 2;
while (i >= j * j) { // after j ^ 2
if (k > dp[i - j * j] + 1) {
k = dp[i - j * j] + 1;
}
j ++;
}
dp[i] = k;
}
k = dp[n];
free(dp);
return k;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int numSquares(int n) {
static vector<int>dp(1, 0);
for(int i = dp.size(); i < = n; i++){
dp.push_back(INT_MAX);
for(int j = 1; j * j < = i; j++)
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
return dp[n];
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i < = n; i++) {
int min = Integer.MAX_VALUE;
for (int j = 1; i - j * j >= 0; j++) {
min = Math.min(min, dp[i - j * j] + 1);
}
dp[i] = min;
}
return dp[n];
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const numSquares = function(n) {
const dp = new Array(n+1).fill(Number.MAX_VALUE)
dp[0] = 0
for(let i = 1; i < = n; i++) {
let min = Number.MAX_VALUE
let j = 1
while(i - j*j >= 0) {
min = Math.min(min, dp[i-j*j] + 1)
++j
}
dp[i] = min
}
return dp[n]
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numSquares(self, n):
q, move = {i ** 2 for i in range(1, int(n ** 0.5) + 1)}, 1
coins = set(q)
while q:
if n in q: return move
q = {sm + c for sm in q for c in coins} - q
move += 1
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0279_PerfectSquares
{
public int NumSquares(int n)
{
var dp = new int[n + 1];
dp[0] = 0;
for (int i = 1; i < = n; i++)
{
int j = 1, min = int.MaxValue;
while (i - j * j >= 0)
{
min = Math.Min(min, dp[i - j * j]);
j++;
}
dp[i] = min + 1;
}
return dp[n];
}
}
}
Input
Output