⏹️Perfect Sqaures

Question (LC.279)

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. For example, 1, 4, 9, 16, ...

Examples

I: n = 12
O: 3 (4 + 4 + 4) 

I: n = 13
O: 2 (9 + 4)

Approach

A simple greedy approach won't work. A counter example is 12 where len(9 + 1 + 1 + 1) < len(4 + 4 + 4). The solution needs to be found recursively for each square root. We can see that some subproblems overlap here. Memoization can reduce the run time.

Brute Force Recursion

def numSquares(self, n: int) -> int:
    min_count = self.search_squares_helper(n)
    return min_count

def search_squares_helper(self, n: int) -> int:
    # base case
    if n == 0:
        return 0

    # recursive calls 
    float_root = math.sqrt(n)
    biggest_root = int(math.floor(float_root))

    min_count = 10001
    for root in range(biggest_root, 0, -1):
        count = 1 + self.search_squares_helper(n - root**2)
        min_count = min(count, min_count)

    return min_count

This is an exponential algo. TLE at n = 41.

Memoized Recursion

def numSquares(self, n: int) -> int:
    memo: Dict[int, int] = {}
    min_count = self.search_squares_helper(n, memo)
    return min_count

def search_squares_helper(self, n: int, memo: Dict[int, int]) -> int:
    # base case
    if n == 0:
        return 0
    
    if n in memo:
        return memo[n]

    # recursive calls
    float_root = math.sqrt(n)
    biggest_root = int(math.floor(float_root))

    min_count = 10001
    for root in range(biggest_root, 0, -1):
        count = 1 + self.search_squares_helper(n - root**2, memo)
        min_count = min(count, min_count)
    memo[n] = min_count
    
    return min_count

This gets the run time down to the number of subproblems which are bounded by the input value. However, recursion has some overhead. OJ gives TLE when n = 8405.

DP

def numSquares(self, n: int) -> int:
    dp: List[int] = [10001 for i in range(n + 1)]
    
    # init
    dp[0] = 0
    dp[1] = 1
    
    # topo order 
    for i in range(2, n + 1):
        # recursive step 
        biggest_root = math.floor(math.sqrt(i))
        for root in range(1, int(biggest_root) + 1):
            dp[i] = min(dp[i], 1 + dp[i - root * root])
    
    # final answer
    return dp[n]

time O(n * sqrt(n)) space O(n)

Reading

• Wikipedia - Lagrange's four-square theorem