# Perfect Squares | LeetCode | Solution Explained

279. Perfect Squares on LeetCode is a mathematical problem, requiring us to pair math with algorithms. I explore how we can do that using Dynamic Programming (DP) and BFS. Problem Link.

## Perfect Squares: Logic

We know that mathematically we can break it down as:

• a, b, c, … represent the coefficients
• we have to minimize the sum of the coefficients

The first thing I wanted to do was to try and restrict the range of x. How far can it go, when we have n restricting it?

We can do `x = (int)sqrt(n)` to find the x value in an instant. This takes `O(log(n))` time & `O(1)` space. Time is because Python calculates square roots using Newton’s method. Here’s a math.stackexchange link.

Let’s take an example. When n = 120, we have sqrt(120) as 10.95… which is 10 in terms of int value. Thus, we can try and break down the 120 value example of 12 having multiple paths for the perfect square question

Clearly, we can have multiple paths. How do we know the best one? When we are making a decision between the first 2 or 3, we don’t know what would happen in the future. How can we see into the future? if you have been following me, you know its the cue for recursion!

## Perfect Squares: Recursive DP Code

```class Solution:
def numSquares(self, n: int) -> int:
@lru_cache(None)
def recurse(n):
if n == 0: return 0

x = (int)(sqrt(n))
count = inf
for i in reversed(range(1, x+1)):
if n - i*i >= 0:
temp = recurse(n - i*i)
count = min(count, temp + 1)
return count

return recurse(n)
```

## Modified Recursive DP Code for Manual DP

```class Solution:
def numSquares(self, n: int) -> int:
# @lru_cache(None) no need now
def recurse(n):
if dp[n] != inf: return dp[n]

if n == 0: return 0

x = (int)(sqrt(n))
count = inf
for i in reversed(range(1, x+1)):
if n - i*i >= 0:
temp = recurse(n - i*i)
count = min(count, temp + 1)

dp[n] = count
return dp[n]

dp = [inf]*(n+1)
return recurse(n)```

## Perfect Squares: BFS Solution

The above solutions were using dfs. What if we used BFS instead? Think about why that is better. I have explained it in my video solution.

```class Solution:
def numSquares(self, n: int) -> int:
sq = [i*i for i in range(1, (int)(sqrt(n))+1)]

explore = {n}
count = 0
while explore:
count += 1
temp = set()
for n in explore:
for x in sq:
if n - x == 0:
return count
if n - x > 0:
explore = temp

return count```
##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Seats | InterviewBit | Solution Explained

June 13, 2022

##### Meeting Rooms | InterviewBit | Solution Explained

June 13, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.