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

Function Signature:

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.
    """
    # Your code here

Example:

# Input: n = 12
# Output: 3
# Explanation: 12 = 4 + 4 + 4.

# Input: n = 13
# Output: 2
# Explanation: 13 = 4 + 9.

# Input: n = 0
# Output: 0

# Input: n = 1
# Output: 1
# Explanation: 1 is a perfect square number

# Input: n = 4
# Output: 1
# Explanation: 4 is a perfect square number

# Input: n = 5
# Output: 2
# Explanation: 5 = 1 + 4

Note:

  • You have to find the least number of perfect square numbers, not the perfect square numbers themselves.

Instructions:

  • Write the num_squares function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊