Perfect Squares

Medium
322.

Perfect Squares

Perfect Squares is a medium coding problem on dynamic programming, math and breadth-first search, asked in Amazon, Google, Adobe and Meta interviews.

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

A perfect square is the product of an integer with itself: 1, 4, 9, 16, …

Example 1

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

Example 2

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

Example 3

Input
n = 1
Output
1

Constraints

  • 1 <= n <= 300
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Perfect Squares — Solution in Python, Java & C++

Perfect Squares solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Perfect Squares is a medium coding problem on dynamic programming, math and breadth-first search, asked in Amazon, Google, Adobe and Meta interviews.

Problem statement

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

A perfect square is the product of an integer with itself: 1, 4, 9, 16, …

Example 1

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

Example 2

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

Example 3

Input: n = 1
Output: 1

Constraints

  • 1 <= n <= 300

Hints for Perfect Squares

  1. Hint 1

    This is an unbounded coin-change problem where the coins are the perfect squares up to n.

  2. Hint 2

    dp[i] = 1 + min(dp[i - k²]) over every k with k² <= i.

  3. Hint 3

    Lagrange's four-square theorem guarantees the answer is always 1, 2, 3 or 4.

How to solve Perfect Squares

Unbounded coin change where the coins are the perfect squares: dp[i] = 1 + min(dp[i - k²]) over every k² ≤ i.

Approach

  1. Set dp[0] = 0 and everything else to a large value.
  2. For each i, try every square k² ≤ i and take the minimum.
  3. Return dp[n].

Why it works

The last square in an optimal representation of i is some k², leaving an optimal representation of i - k²; the recurrence tries every last square.

Complexity

  • Time — O(n · √n)
  • Space — O(n)

Pitfalls

  • Lagrange's theorem bounds the answer at 4; a number-theory shortcut exists but the DP is the expected approach.

Reference solution

Python

def numSquares(n: int) -> int:
    dp = [0] + [n + 1] * n
    for i in range(1, n + 1):
        k = 1
        while k * k <= i:
            dp[i] = min(dp[i], dp[i - k * k] + 1)
            k += 1
    return dp[n]

Java

public static int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, n + 1);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k * k <= i; k++) {
            dp[i] = Math.min(dp[i], dp[i - k * k] + 1);
        }
    }
    return dp[n];
}

C++

int numSquares(int n) {
    vector<int> dp(n + 1, n + 1);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k * k <= i; k++) {
            dp[i] = min(dp[i], dp[i - k * k] + 1);
        }
    }
    return dp[n];
}

JavaScript

var numSquares = function(n) {
    const dp = new Array(n + 1).fill(n + 1);
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let k = 1; k * k <= i; k++) {
            if (dp[i - k * k] + 1 < dp[i]) dp[i] = dp[i - k * k] + 1;
        }
    }
    return dp[n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Breadth-First Search (BFS)