Perfect Squares - Practice Coding Problems

Perfect Squares - 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.

Input & Output

Example 1 — Basic Case

$ Input: n = 12

› Output: 3

💡 Note: 12 = 4 + 4 + 4. We need 3 perfect squares (each is 2²), so return 3.

Example 2 — Single Square

$ Input: n = 13

› Output: 2

💡 Note: 13 = 9 + 4 = 3² + 2². We need 2 perfect squares, so return 2.

Example 3 — Already Perfect Square

$ Input: n = 16

› Output: 1

💡 Note: 16 = 4² is already a perfect square, so we need only 1 perfect square.

Constraints

1 ≤ n ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n = 12

Process

Find minimum perfect squares that sum to 12

Output

Return 3 (since 12 = 4 + 4 + 4)

Key Takeaway

🎯 Key Insight: Use dynamic programming to build optimal solutions for each number from 1 to n

Asked in

G Google 45 a Amazon 38 f Facebook 25 M Microsoft 20

The key insight is that this is a classic dynamic programming problem where each number can be built optimally from smaller perfect squares. Best approach is Bottom-Up DP which builds solutions iteratively. Time: O(n√n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n√n)	O(n)	Cache recursive results to avoid recomputation
Bottom-Up Dynamic Programming	O(n√n)	O(n)	Build solutions from smaller numbers up to n
Breadth-First Search	O(n√n)	O(n)	BFS to find shortest path from 0 to n
Recursive Brute Force	O(n^(n/2))	O(n)	Try all possible combinations of perfect squares recursively

Memoization (Top-Down DP) — Algorithm Steps

Create memo table
Before recursing, check if result already computed
Store and return computed results

Visualization

Tap to expand

Step-by-Step Walkthrough

Compute

Calculate result for each subproblem once

Store

Cache result in memo table

Reuse

Return cached result on repeat calls

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int memo[10001];
int squares[100];
int squareCount;

int helper(int remaining) {
    if (remaining == 0) return 0;
    if (memo[remaining] != -1) return memo[remaining];
    
    int minCount = INT_MAX;
    for (int i = 0; i < squareCount; i++) {
        if (squares[i] > remaining) break;
        int count = 1 + helper(remaining - squares[i]);
        if (count < minCount) {
            minCount = count;
        }
    }
    
    memo[remaining] = minCount;
    return minCount;
}

int solution(int n) {
    if (n <= 0) return 0;
    
    // Initialize memo table
    memset(memo, -1, sizeof(memo));
    
    // Find perfect squares
    squareCount = 0;
    for (int i = 1; i * i <= n; i++) {
        squares[squareCount++] = i * i;
    }
    
    return helper(n);
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n√n)

Each of n subproblems solved once, each tries √n perfect squares

✓ Linear Growth

Space Complexity

O(n)

Memo table stores n values plus recursion stack depth n

⚡ Linearithmic Space

67.0K Views

High Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization (Top-Down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler