Perfect Squares

MEDIUM

Description

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.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

1 <= n <= 10⁴

Approaches

Checkout 3 different approaches to solve Perfect Squares. Click on different approaches to view the approach and algorithm in detail.

Recursive Approach

Use recursion to try all possible combinations of perfect squares that sum up to n.

Algorithm

Create a recursive helper function that takes the remaining number n
Base cases:
- If n is 0, return 0
- If n is negative, return MAX_VALUE
For each number i from 1 to sqrt(n):
- Subtract i*i from n
- Recursively find minimum squares for remaining number
- Update minimum if a valid solution is found
Return minimum + 1

This approach uses recursion to find all possible combinations of perfect squares that sum up to n. For each number from 1 to sqrt(n), we try subtracting its square from n and recursively find the minimum number of perfect squares needed for the remaining number.

class Solution {
    public int numSquares(int n) {
        if (n <= 0) return 0;
        return recursiveHelper(n);
    }
    
    private int recursiveHelper(int n) {
        if (n == 0) return 0;
        if (n < 0) return Integer.MAX_VALUE;
        
        int min = Integer.MAX_VALUE;
        for (int i = 1; i * i <= n; i++) {
            int result = recursiveHelper(n - i * i);
            if (result != Integer.MAX_VALUE) {
                min = Math.min(min, result + 1);
            }
        }
        return min;
    }
}

Complexity Analysis

Time Complexity: O(n^(h/2)) where h is the height of recursion treeSpace Complexity: O(sqrt(n)) for recursion stack

Pros and Cons

Pros:

Simple to understand and implement
Works for small inputs

Cons:

Exponential time complexity
Stack overflow for large inputs
Many redundant calculations

Code Solutions

Checking out 3 solutions in different languages for Perfect Squares. Click on different languages to view the code.

class Solution { public int numSquares ( int n ) { int m = ( int ) Math . sqrt ( n ); int [] f = new int [ n + 1 ]; Arrays . fill ( f , 1 << 30 ); f [ 0 ] = 0 ; for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = i * i ; j <= n ; ++ j ) { f [ j ] = Math . min ( f [ j ], f [ j - i * i ] + 1 ); } } return f [ n ]; } }

Video Solution

Watch the video walkthrough for Perfect Squares

Algorithms:

Breadth-First Search

Patterns:

MathDynamic Programming

Companies:

Accenture |Walmart Labs |Yandex |Citadel |