Back to problems
Leetcode
Medium
Dynamic Programming
Math
Number Theory
Perfect Squares
Return the minimum number of perfect square numbers whose sum is exactly n.
Acceptance 0%
Problem Statement
Perfect Squares
Given a positive integer n, find the minimum number of perfect square numbers whose sum is exactly n.
A perfect square is an integer of the form k^2 where k is a positive integer.
Your task is to choose as few squares as possible while still summing to n.
Input Format
- A single integer
n.
Output Format
- Return the minimum count of perfect squares whose sum is
n.
Constraints
1 <= n- The exact upper bound may vary by platform, but the intended solution should work efficiently for typical interview-sized values.
Hints
- Try building answers for smaller values first.
- Each state can consider subtracting one perfect square and reusing a previously computed result.
- You may also think of this as an unbounded choice problem where each square can be used multiple times.
Input Format
- A single integer
n.
Output Format
- Return the minimum number of perfect squares that sum to
n.
Constraints
1 <= n- Solve efficiently for interview-sized inputs.
Examples
Sample cases returned by the problem API.
Example 1
Input
n = 12
Output
3
Explanation
12 = 4 + 4 + 4, so the minimum count is 3.
Example 2
Input
n = 13
Output
2
Explanation
13 = 4 + 9, so the minimum count is 2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.
Guided hints
Editorial and discussion links
Concept map and variants
Track your progress
Sign in to bookmark this problem, save notes, and manage its revision plan.