We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Perfect Squares

Number: 279

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft, Yandex, Bloomberg, Citadel, Adobe, Apple, Accenture, Uber, Yahoo

Problem Description

Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer which is the square of another integer (for example, 1, 4, 9, 16, ...).

Key Insights

  • The problem is similar to making change with coins, where the "coins" are the perfect squares.
  • Dynamic Programming (DP) is an effective approach by building up the solution for each number from 1 to n.
  • Breadth-First Search (BFS) can also be used to treat each sum as a state and find the shortest path.
  • The constraint 1 <= n <= 10^4 allows an O(n * sqrt(n)) solution to be efficient.

Space and Time Complexity

Time Complexity: O(n * sqrt(n))
Space Complexity: O(n)

Solution

The solution uses dynamic programming. We construct an array dp where dp[i] represents the minimum number of perfect squares that sum up to i. For each number i from 1 to n, we iterate over all perfect squares jj that are less than or equal to i and update dp[i] to be the minimum of its current value or 1 + dp[i - jj]. This builds up the solution from the base case dp[0] = 0.

Code Solutions

# Python solution using dynamic programming

def numSquares(n: int) -> int:
    # Initialize dp array where dp[i] indicates the least number of perfect squares summing to i.
    dp = [float('inf')] * (n + 1)
    dp[0] = 0  # Base case: 0 perfect squares sum to 0

    # Iterate through each number from 1 to n
    for i in range(1, n + 1):
        # Try every perfect square number j*j less than or equal to i
        j = 1
        while j * j <= i:
            # Update dp[i] with the minimum count found so far
            dp[i] = min(dp[i], dp[i - j*j] + 1)
            j += 1

    return dp[n]

# Example usage:
# print(numSquares(12))  # Output: 3
# print(numSquares(13))  # Output: 2
← Back to All Questions