Skip to main content

279. Perfect Squares

medium

Find the minimum number of perfect-square integers that sum to n. The unbounded-knapsack flavor of coin change — each square is a coin you can reuse.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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 product of some integer with itself; for example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Constraints

  • 1 <= n <= 10^4

Examples

Example 1

Input
n = 12
Output
3

Explanation: 12 = 4 + 4 + 4.

Example 2

Input
n = 13
Output
2

Explanation: 13 = 4 + 9.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Let dp[i] = min squares summing to i. The recurrence considers every square <= i.

Hint 2

dp[i] = 1 + min over k of dp[i - k*k]. Base case dp[0] = 0.

Hint 3

BFS over states 0..n with edges labeled by squares is the iterative-DP framing.

Solution approach

Reveal approach

Define dp[i] as the minimum number of perfect squares summing to i, with dp[0] = 0. For each i from 1 to n, try every j with j*j <= i and set dp[i] = min(dp[i], dp[i - j*j] + 1). Return dp[n]. Time is O(n * sqrt(n)) because the inner loop runs up to floor(sqrt(i)) times. Space is O(n). An equivalent BFS framing treats states 0..n as nodes with edges of label k*k, finding the shortest path length from 0 to n — useful intuition but the DP is cleaner to code.

Complexity

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

Related patterns

  • dynamic-programming
  • bfs
  • unbounded-knapsack

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

More DP 1D practice problems

See all DP 1D problems →