Problem 279

(Last updated: )

Question statement:

Given an integer n, return the least number of perfect square numbers that sum to n.

Solution

Main idea

Approach 1: This is a 1-d DP problem, where we make a dp array of length n+1, initialized to infinity at all spot. Let dp[0]=0, and dp[1]=1. At dp[i] we store the least number of perfect squares that sum to i. Now we list all the perfect squares less than n, and for each i, we iterate through this perfect squares array, breaking out if i-perfect_squares[i] < 0, otherwise, we set dp[i] = min(dp[i], dp[i-perfect_squares[i]]). Then we simply return dp[-1].

Approach 2: This approach utilizes the Lagrange four squares theorem anf Legendre’s three square theorem. The former says that any non-negative integer can be represented as a sum of four perfect squares, while the latter says that a non-negative integer is written as a sum of three perfect squares if and only if the number is NOT of the form $4^a(8b+7)$. Thus if a number is of this form, then it has to be written as a sum of four squares. Finally, if the number given is a square number, we return 1. We scan through perfect_squares and check if n - perf_squares[i] is a perfect_square, and if it is, we return 2. Finally, if we are not in any of the above conditions, we return 3.

Code:

Approach 1:

1
2
3
4
5
6
7
8
9
10
11
12
def numSquares(self, n: int) -> int:
    perf_squares = [i**2 for i in range(1,int(sqrt(n))+1)]
    dp = [float('inf') for _ in range(n+1)]
    dp[0] = 0
    dp[1] = 1
    for i in range(2,n+1):
        for j in perf_squares:
            if(i-j < 0):
                break
            else:
                dp[i] = min(dp[i], 1+dp[i-j])
    return dp[-1]

Approach 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
def numSquares(self, n: int) -> int:
    perf_squares = set([i**2 for i in range(1,int(sqrt(n))+1)])
    if(int(sqrt(n))**2 == n):
        return 1
    for i in perf_squares:
        if(n-i in perf_squares):
            return 2
    while(n % 4) == 0:
        n=n/4
    if(n % 8 == 7):
        return 4
    else:
        return 3

Comments:

Time complexity for approach 1: O($n\sqrt{n}$)
Time complexity for approach 2: O($\sqrt{n}$)

At the time of submission, the the first solution passes leetcode submission cases in 2352ms, beats 62.81% of users. It uses 16.82MB of memory, beating 74.60% of users.
At the time of submission, the the second solution passes leetcode submission cases in 45ms (!!), beats 98.18% of users. It uses 16.44MB of memory, beating 92.57% of users.