algoadvance

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

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 8 are not.

Example 1:

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

Example 2:

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

Clarifying Questions

  1. Range of n: What is the range of the integer n? (The typical constraint in such problems is to ensure optimization concerns are clear.)
  2. Input Validity: Can n be a negative number or zero? Usually, n is assumed positive.
  3. Single Output: Should we only consider the minimum number of perfect squares, or are there cases where multiple solutions exist?

Let’s proceed with the assumption that n is a positive integer, and we need to find the least number of perfect squares summing to n.

Strategy

To solve the problem, a common approach is to use dynamic programming (DP). Here’s the strategy in brief:

  1. DP Array Initialization:
    • Create a DP array dp where dp[i] will store the least number of perfect squares that sum up to i.
    • Initialize the DP array with infinity for all i, except dp[0] which is 0 (because zero numbers are needed to sum up to zero).
  2. Building the DP Array:
    • For each number i from 1 to n, consider all perfect squares j^2 (where j^2 <= i).
    • Update the DP array using the recurrence relation: dp[i] = min(dp[i], dp[i - j^2] + 1)
  3. Result:
    • The answer to the problem will be dp[n].

Dynamic Programming Code

def numSquares(n: int) -> int:
    import math
    
    # Create DP array with initially infinite values
    dp = [float('inf')] * (n + 1)
    dp[0] = 0  # Base case
    
    # List of all perfect squares less than or equal to `n`
    max_square_index = int(math.isqrt(n)) + 1
    squares = [i * i for i in range(1, max_square_index)]
    
    for i in range(1, n + 1):
        for square in squares:
            if i < square:
                break
            dp[i] = min(dp[i], dp[i - square] + 1)
    
    return dp[n]

Time Complexity

This solution efficiently finds the least number of perfect squares that sum to a given integer n using dynamic programming.

Try our interview co-pilot at AlgoAdvance.com