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 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 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

More Math practice problems

See all Math problems →