Least number of perfect square numbers that sums upto n

Question

The question is:

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Link to the question

Example

Given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

NOTE

The approach i have taken is similar to an Integer Knapsack problem with duplicates allowed. First i calculated all the perfect squares which are less than equal to the number n. Now once i have them, the problem is similar to the Integer Knapsack problem. I have a number n and a list of numbers. i want to choose minimum number of numbers from the list such that their sum is equal to n. This problem has a DP solution which i have used.

Out of 586 test cases, i passed 562 test cases and got TLE on the next one. The value of n for that testcase is 3428.

The solution i submitted:

class Solution(object):
    def numSquares(self,n):
        if(n == 0):
            return 0
        if(n == 1):
            return 1
        squares = self.findSquares(n) # returns a list of perfect squares <= n
        rows = len(squares)
        cols = n + 1
        mat = []
        for i in range(rows):
            mat.append([0] * cols)

        for i in range(cols):
            mat[0][i] = i

        for i in range(rows):
            mat[i][0] = 0

        min = mat[0][cols - 1]
        for i in range(1,rows):
            for j in range(1,cols):
                if(j < squares[i]):
                    mat[i][j] = mat[i - 1][j]

                else:
                    mat[i][j] = self.min(mat[i - 1][j], (j // squares[i] + (mat[i][j % squares[i]])))
                if(j == cols - 1 and mat[i][j] < min):
                    min = mat[i][j]
        '''
        for i in range(rows):
            for j in range(cols):
                print(mat[i][j],end=" ")
            print()
            '''
        return min

    def min(self,a,b):
        if(a <= b):
            return a
        else:
            return b


    def findSquares(self,n):

        i = 1
        squares = []
        while (i * i <= n):
            squares.append(i * i)
            i = i + 1
        return squares
'''
x = Solution()

print(x.numSquares(43))
'''

Thanks in advance.

Answer 1

You can simplify your solution to:

def numSquares(self,n):
    if(n == 0):
        return 0
    if(n == 1):
        return 1
    squares = self.findSquares(n)
    rows = len(squares)
    cols = n + 1
    mat = [n] * cols
    mat[0] = 0

    for s in squares:
        for j in range(s,cols):
            mat[j] = min(mat[j], 1 + mat[j - s])

    return mat[n]

This avoids using:

1. the self.min function
2. the division/modulus operation in the inner loop.
3. the 2d array

and is about twice as fast.

Answer 2

A bit late, but I believe this answer can help others as it did me. This below is the fastest solution possible with O(sqrt(n)) time complexity

It is based on Lagrange’s four-square theorem every natural number can be represented as the sum of four integer squares. So the answer set would be 1, 2, 3 or 4.

class Solution:
    def is_perfect(self, n):
        x = int(math.sqrt(n))
        return x * x == n

    def numSquares(self, n: int) -> int:
        if n < 4:
            return n

        if self.is_perfect(n):  # number is a perfect square
            return 1

        # the result is 4 if number = 4^k*(8*m + 7)
        while n & 3 == 0:  # while divisible by 4
            n >>= 2
        if n & 7 == 7:  # 8m+7 => last 3 digits = 111
            return 4

        x = int(math.sqrt(n))
        for i in range(1, x + 1):  # sum of 2 perfect squares
            if self.is_perfect(n - i * i):
                return 2

        return 3  # by elimination