Skip to main content

279. Perfect Squares

medium

Find the least number of perfect-square integers that sum to n. A textbook DP problem with a deep math shortcut: Lagrange's four-square theorem guarantees the answer is always in {1, 2, 3, 4}.

By Alex Chen, 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 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 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

Bottom-up DP: dp[i] = least number of squares summing to i. Base case dp[0] = 0.

Hint 2

Transition: dp[i] = 1 + min over all j with j*j <= i of dp[i - j*j].

Hint 3

O(n * sqrt(n)) overall — fast enough for n <= 10000.

Hint 4

Math shortcut: Lagrange's four-square theorem says every positive integer is the sum of at most 4 squares. Legendre's theorem says it needs 4 iff n = 4^a * (8b + 7). So the answer is always 1, 2, 3, or 4 — check those cases in O(sqrt(n)).

Solution approach

Reveal approach

DP approach: dp[0] = 0; for i in 1..n compute dp[i] = 1 + min(dp[i - j*j]) over all j*j <= i. Return dp[n]. O(n * sqrt(n)) time, O(n) space — comfortably fast for n <= 10^4. Math shortcut: by Lagrange's four-square theorem the answer is at most 4. Check (1) is n itself a perfect square? Return 1. (2) Is n = a^2 + b^2 for some a, b? Return 2. (3) By Legendre's three-square theorem, n needs 4 iff n / 4^a = 8b + 7 for some integers a >= 0, b >= 0 — check that. Else return 3. O(sqrt(n)) time, O(1) space.

Complexity

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

Related patterns

  • dynamic-programming
  • math
  • bfs

Related problems

Asked at

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

  • Amazon
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Perfect Squares and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →