Last updated on October 5th, 2024 at 04:29 pm

Here, We see ** Perfect Squares LeetCode Solution**. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

*List of all LeetCode Solution*

*List of all LeetCode Solution*

## Topics

Breadth First Search, Dynamic Programming, Math

## Companies

## Level of Question

Medium

**Perfect Squares LeetCode Solution**

## Table of Contents

**Problem Statement**

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.

**1. Perfect Squares Leetcode Solution C++**

class Solution { public: int numSquares(int n) { if (n <= 0) { return 0; } vector<int> cntPerfectSquares(n + 1, INT_MAX); cntPerfectSquares[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j*j <= i; j++) { cntPerfectSquares[i] = min(cntPerfectSquares[i], cntPerfectSquares[i - j*j] + 1); } } return cntPerfectSquares.back(); } };

**2. Perfect Squares Leetcode Solution Java**

class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; int count = 1; while (count * count <= n) { int sq = count * count; for (int i = sq; i <= n; i++) { dp[i] = Math.min(dp[i - sq] + 1, dp[i]); } count++; } return dp[n]; } }

**3. Perfect Squares Leetcode Solution JavaScript**

var numSquares = function(n) { let dp = new Array(n + 1).fill(Infinity); dp[0] = 0; for (let i = 1; i <= n; ++i) { let min_val = Infinity; for (let j = 1; j * j <= i; ++j) { min_val = Math.min(min_val, dp[i - j * j] + 1); } dp[i] = min_val; } return dp[n]; };

**4. Perfect Squares Leetcode Solution Python**

class Solution(object): def numSquares(self, n): dp = [float('inf')] * (n + 1) dp[0] = 0 count = 1 while count * count <= n: sq = count * count for i in range(sq, n + 1): dp[i] = min(dp[i - sq] + 1, dp[i]) count += 1 return dp[n]