Solution 1: Dynamic Programming

Here’s a Python implementation of the num_squares function using dynamic programming:

def num_squares(n: int) -> int:
    # Initialize an array to store the minimum number of perfect squares needed for each value up to n
    dp = [float('inf')] * (n + 1)

    # Base case: 0 perfect squares needed for 0
    dp[0] = 0

    # Iterate from 1 to n
    for i in range(1, n + 1):
        # Check all possible perfect squares less than or equal to i
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1

    return dp[n]

# Example usage:
result = num_squares(12)
print(result)  # Output: 3

result = num_squares(13)
print(result)  # Output: 2

result = num_squares(0)
print(result)  # Output: 0

result = num_squares(1)
print(result)  # Output: 1

result = num_squares(4)
print(result)  # Output: 1

result = num_squares(5)
print(result)  # Output: 2

This solution uses dynamic programming to build an array dp, where dp[i] represents the least number of perfect squares needed to sum up to i.

Time Complexity:

  • The time complexity of this solution is O(n * sqrt(n)), where n is the given positive integer.
  • We iterate over each number from 1 to n and for each number, we iterate over perfect square numbers less than or equal to it, which takes O(sqrt(n)) time.

Space Complexity:

  • The space complexity is O(n) because we use an additional dp array of size n+1.

Another approach to solve this problem is by using Breadth-First Search (BFS) algorithm. We can consider the given positive integer n as the root.

Here’s how we can implement this approach:

import math
from collections import deque

def num_squares(n: int) -> int:
    """
    Return the least number of perfect square numbers that sum up to n.

    Parameters:
    - n: A positive integer.

    Returns:
    - int: The least number of perfect square numbers.
    """
    # List to store perfect square numbers less than or equal to n
    squares = [i * i for i in range(1, int(math.sqrt(n)) + 1)]
    
    # Set to keep track of visited numbers
    visited = set()
    
    # Initialize queue for BFS traversal
    queue = deque([(n, 0)])  # (number, level)
    
    # Perform BFS traversal
    while queue:
        num, level = queue.popleft()
        for square in squares:
            if num - square == 0:
                return level + 1
            elif num - square > 0 and (num - square) not in visited:
                visited.add(num - square)
                queue.append((num - square, level + 1))
    
    return 0  # No perfect square numbers sum up to n

# Example usage:
print(num_squares(12))  # Output: 3
print(num_squares(13))  # Output: 2
print(num_squares(0))   # Output: 0
print(num_squares(1))   # Output: 1
print(num_squares(4))   # Output: 1
print(num_squares(5))   # Output: 2

Time Complexity:

Let’s break down the time complexity analysis for the num_squares function:

  1. Precomputing Perfect Square Numbers:
    • We precompute the list of perfect square numbers less than or equal to n, which requires iterating up to the square root of n.
    • This precomputation step takes O(sqrt(n)) time.
  2. Breadth-First Search (BFS) Traversal:
    • In the worst case, each number from n to 1 is visited once.
    • For each number, we iterate over the perfect square numbers less than or equal to it.
    • Since the number of perfect square numbers less than or equal to n is also bounded by sqrt(n), the overall time complexity of the BFS traversal is O(n * sqrt(n)).
  3. Overall Time Complexity:
    • Combining the time complexity of precomputing perfect square numbers and the BFS traversal, the overall time complexity is dominated by the BFS traversal, which is O(n * sqrt(n)).

Therefore, the time complexity of the num_squares function is O(n * sqrt(n)), where n is the given positive integer. This complexity arises from the iteration over each number from n to 1 and for each number, the iteration over perfect square numbers less than or equal to it.

Space Complexity:

Let’s analyze the space complexity of the num_squares function:

  1. Perfect Square Numbers List:
    • We create a list of perfect square numbers less than or equal to n, which requires storing these numbers in memory.
    • Since the number of perfect square numbers less than or equal to n is bounded by sqrt(n), the space complexity of storing this list is O(sqrt(n)).
  2. Visited Set:
    • We use a set to keep track of visited numbers during the BFS traversal to avoid revisiting the same number.
    • In the worst case, all numbers from n to 1 are visited, so the size of the visited set could be up to n.
    • Therefore, the space complexity of the visited set is O(n).
  3. Queue for BFS Traversal:
    • We use a deque to perform BFS traversal, which stores tuples of (number, level).
    • In the worst case, the queue may contain all numbers from n to 1, so the size of the queue could be up to n.
    • Therefore, the space complexity of the queue is also O(n).
  4. Overall Space Complexity:
    • Combining the space used by the perfect square numbers list, visited set, and queue, the overall space complexity is O(sqrt(n)) + O(n) + O(n), which simplifies to O(n).

Therefore, the space complexity of the num_squares function is O(n), where n is the given positive integer. This complexity arises from storing the list of perfect square numbers, the visited set, and the queue for BFS traversal.

Solution 3: Lagrange’s Four-square Theorem

There is another solution known as Lagrange’s four-square theorem. This theorem states that every natural number can be represented as the sum of at most four square numbers. Based on this theorem, we can solve the problem as follows:

  • Check if the number is a perfect square: If n itself is a perfect square, then it can be represented as a single perfect square number, so return 1.
  • Check if the number can be represented as the sum of two perfect squares: If n - i*i is a perfect square for any i from 1 to sqrt(n), then n can be represented as the sum of two perfect square numbers. In this case, return 2.
  • Check if the number can be represented as the sum of three perfect squares: This step involves using a double loop. For each i and j, where i and j iterate from 1 to sqrt(n), check if n - i*i - j*j is a perfect square. If it is, then return 3.
  • If none of the above conditions are met: Return 4, as per Lagrange’s theorem.

Here’s how we can implement this approach:

import math

def num_squares(n: int) -> int:
    """
    Return the least number of perfect square numbers that sum up to n.

    Parameters:
    - n: A positive integer.

    Returns:
    - int: The least number of perfect square numbers.
    """
    # determine whether a number is a perfect square
    def perfect_square(m: int) -> bool:
        return m == int(math.sqrt(m))**2
    
    # 0 perfect squares needed for 0
    if n == 0:
        return 0

    # Check if n itself is a perfect square
    if perfect_square(n):
        return 1
    
    # Check if n can be represented as the sum of two perfect squares
    sqrt_n = int(math.sqrt(n))
    for i in range(1, sqrt_n + 1):
        if perfect_square(n - i*i):
            return 2
    
    # Check if n can be represented as the sum of three perfect squares
    for i in range(1, sqrt_n + 1):
        for j in range(1, sqrt_n + 1):
            if perfect_square(n - i*i - j*j):
                return 3
    
    # If none of the above conditions are met, return 4
    return 4

# Example usage:
print(num_squares(12))  # Output: 3
print(num_squares(13))  # Output: 2
print(num_squares(0))   # Output: 0
print(num_squares(1))   # Output: 1
print(num_squares(4))   # Output: 1
print(num_squares(5))   # Output: 2

Time Complexity:

The time complexity of this solution is O(n), where n is the given positive integer.

We perform three iterations:

  • The first loop iterates from 1 to sqrt(n) to check if n itself is a perfect square, which takes O(sqrt(n)) time.
  • The second loop iterates from 1 to sqrt(n) to check if n can be represented as the sum of two perfect squares, which also takes O(sqrt(n)) time.
  • The third nested loop iterates from 1 to sqrt(n) twice to check if n can be represented as the sum of three perfect squares, which takes O(sqrt(n) * sqrt(n)) = O(n) time.

Therefore, the overall time complexity is dominated by the third loop, resulting in O(n).

Space Complexity:

The space complexity of this solution is O(1), i.e., constant space. We use a few variables for iteration and calculation, but they don’t depend on the size of the input n. Hence, the space complexity remains constant, regardless of the value of n.