Perfect Squares

MathDPDFS
https://leetcode.com/problems/perfect-squares

# Import

from math import sqrt

# Solution

TLE

# Brute Force

Exponential runtime. TLE on 55.

def numSquares(self, n: int) -> int:
    square_nums = [i**2 for i in range(1, int(sqrt(n))+1)]

    def minNumSquares(k: int) -> int:
        if k in square_nums:
            return 1
        min_num = sys.maxsize
        # find the minimal value among all possible solutions
        for square in square_nums:
            if k < square:
                break
            min_num = min(min_num, minNumSquares(k-square) + 1)
        return min_num

    return minNumSquares(n)

# Memoized DP - Top Down

def numSquares(self, n: int) -> int:
    square_nums = [i**2 for i in range(1, int(sqrt(n))+1)]
    memo = [sys.maxsize for _ in range(n+1)]
    memo[0] = 0

    def minNumSquares(k: int) -> int:
        if k in square_nums:
            memo[k] = 1
        if memo[k] < sys.maxsize:
            return memo[k]
        # find the minimal value among all possible solutions
        for square in square_nums:
            if k < square:
                break
            memo[k] = min(memo[k], minNumSquares(k-square) + 1)
        return memo[k]

    return minNumSquares(n)

# Memoized DP - Bottom Up

numSquares(n)=min(numSquares(n-k) + 1)ksquare numbers \text{numSquares}(n) = \min \Big(\text{numSquares(n-k) + 1}\Big) \qquad \forall k \in {\text{square numbers}}

Complexity

time: O(nn)O(n\cdot\sqrt{n})
space: O(n)O(n)

def numSquares(self, n: int) -> int:
    square_nums = [i**2 for i in range(1, int(sqrt(n))+1)]
    dp = [sys.maxsize for _ in range(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]

# Greedy Enumeration

Complexity

time: O(nh+11n1)=O(nh2)O(\frac{\sqrt{n}^{h+1} - 1}{\sqrt{n}-1}) = O(n^{\frac{h}{2}})
space: O(n)O(\sqrt{n})

def numSquares(self, n: int) -> int:
    square_nums = set(i**2 for i in range(1, int(sqrt(n))+1))

    def is_divided_by(n, cnt):
        """
        return: true if "n" can be decomposed into "count" number of perfect square numbers.
        e.g. n=12, count=3:  true.
                n=12, count=2:  false
        """
        if cnt == 1:
            return n in square_nums

        for square_num in square_nums:
            remainder = n - square_num
            if is_divided_by(remainder, cnt-1):
                return True
        return False

    for cnt in range(1, n+1):
        if is_divided_by(n, cnt):
            return cnt

# BFS

Use set instead of list for queue to eliminate the redundancy.

Complexity

time: O(nh+11n1)=O(nh2)O(\frac{\sqrt{n}^{h+1} - 1}{\sqrt{n} - 1} ) = O(n^{\frac{h}{2}})
space: O((n)h)=O(nh2)O\Big((\sqrt{n})^h\Big) = O(n^{\frac{h}{2}})

def numSquares(self, n: int) -> int:
    square_nums = [i**2 for i in range(1, int(sqrt(n))+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 # node found
                elif remainder < square_num:
                    break
                else:
                    next_queue.add(remainder - square_num)
        queue = next_queue

    return level

# Math

In 1770, Lagrange's four-square theorem(or Bachet's conjecture) states that every natural number can be represented as the sum of four integer squares.

p=a02+a12+a22+a32where a0,a1,a2,a3 are integersp=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2} \qquad \text{where } a_{0}, a_{1}, a_{2}, a_{3} \text{ are integers}

In 1797, Gauss–Legendre three-square theorem states that nn is a sum of three squares precisely when nn is not of the form 4k(8m+7)4^{k}(8m+7) for any nonnegative integers kk, mm:

n4k(8m+7)n=a02+a12+a22n \ne 4^{k}(8m+7) \iff n = a_{0}^{2}+a_{1}^{2}+a_{2}^{2}

So here is our strategy:

  1. Check if n is of the form 4k(8m+7)4^{k}(8m+7). If yes, return 44
  2. Otherwise, check if n is a perfect square, or a sum of 22 perfect squares
  3. Else, n is a sum of 33 perfect squares
def isSquare(self, n: int) -> bool:
    sq = int(sqrt(n))
    return sq*sq == n

def numSquares(self, n: int) -> int:
    # four-square and three-square theorems
    while (n & 3) == 0:
        n >>= 2      # reducing the 4^k factor from number
    if (n & 7) == 7: # mod 8
        return 4

    if self.isSquare(n):
        return 1
    # check if the number can be decomposed into sum of two squares
    for i in range(1, int(n**(0.5)) + 1):
        if self.isSquare(n - i*i):
            return 2
    # bottom case from the three-square theorem
    return 3