# 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

Let’s take another example. In this case we start with 3.

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: temp.add(n-x) explore = temp return count

### Recommended Posts

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022