[Leetcode] Perfect Squares

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 16are perfect squares while 3and 11are 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 <= 10``4

How to understand?

This is really similar to coin change problem. There are perfect squares like 1,4,9… Make the target sum by using those numbers and get the smallest possible numbers of the used squares.

How to approach?

Brute Force

class Solution(object):
    def numSquares(self, n):
        square_nums = [i**2 for i in range(1, int(math.sqrt(n))+1)]

        def minNumSquares(k):
            if k in square_nums:
                return 1
            min_num = float('inf')

            for square in square_nums:
                if k < square:
                    break
                new_num = minNumSquares(k-square) + 1
                min_num = min(min_num, new_num)
            return min_num

        return minNumSquares(n)

1. create square nums array to save the square number less than n.
2. lastly return minNumSquares(n) to return the smallest possible square numbers to compose sum.
3. create minNumSquares take n to return the min_num at the end.
4. when the parameter k, if it is in the square_nums array then return 1, since it means that the k is square number so it can be added to subtract from sum and +1 to the min_num
5. set the min_num as infinity value.
6. create for loop to iterate over square_nums array. when parameter k is less than the square number then it means it's useless since it exceeds the target number so break the loop.
7. when recursively called the minNumSquares function with the parameter k-square and +1 to the returned value, it's the smallest possible numbers of the square number to sum up to the target.
8. compare the min_num and the returned value from minNumSquares.
9. return the min_num.

summary

it's using function that return the smallest number of square numbers of used to compose target value with the parameter k, it recursively call the function and try to compute every possible value even it is computed before.

DP

class Solution(object):
    def numSquares(self, n):
        square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)]
        
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        
        for i in range(1, n+1):
            for square in square_nums:
                if i < square:
                    break
                dp[i] = min(dp[i], dp[i-square] + 1)
        
        return dp[-1]

1. create square_nums array which store the perfect square numbers that is less than n
2. create n+1 length dp array filled with infinities.
3. set the 0 index item as 0 in dp.
4. dp means how many perfect square numbers is used to sum up the current index number, so 0 index item is 0 since there is no need to add square number to make 0.
5. create for loop using i starting from 1 to n.
6. and create inner for loop using square number in square_nums array.
7. when the i is less than square number it means square number itself exceeds the target number i, so it doesn't need to calculate further, so break the loop.
8. when square is less than i then update dp[i] using minimum comparing between dp[i] and i-square dp index item and add 1 to that value. since the square is used to make the value.
9. lastly return the last index item in dp array.

summary

this is using dp array which stores pre computed value for the smallest square numbers to make the target number(index). Pre computed values are used to make the dp[i].

BFS

class Solution:
    def numSquares(self, n):
        square_nums = [i * i for i in range(1, int(n**0.5)+1)]
    
        level = 0
        queue = {n}
        while queue:
            level += 1
            next_queue = set()

            for remainder in queue:
                for square_num in square_nums:    
                    if remainder == square_num:
                        return level 
                    elif remainder < square_num:
                        break
                    else:
                        next_queue.add(remainder - square_num)
            queue = next_queue
        return level

1. create square_nums array to store the perfect square numbers below n.
2. and create level as 0 and also set of queue using n.
3. while queue has size, increment level by 1, since its layer is plused.
4. and create the next_queue using set.
5. and create for loop using remainder in queue and inner for loop using square in square_nums.
6. when remainder is the square_num then return the level since it reached target number using smallest number of square numbers.
7. if the remainder in queue is smaller then square_num then break the loop since it's not valid when the remainder is bigger than the square number.
8. other than that add the remainder-square_num to the next_queue set
9. and lastly update the queue as next_queue to check the remainder in the next level.
10. and lastly return the level if there is no item in the queue.

summary

use the level and queue to check all the possible nodes layer by layer. using BFS to check if the path is valid and if it's not valid, there is no further calculation for the path. This make the optimal solution to find the smallest path to reach the target number using the square numbers.