Get Minimum Squares

JavaView on GFG

Problem Overview

Minimum number of perfect squares summing to n.

See our study guide for structured GFG and LeetCode practice.

Intuition

Minimum number of perfect squares summing to n. BFS or DP.

Algorithm

1DP: dp[i] = min(dp[i - j*j] + 1) for all j where j*j <= i. Base: dp[0]=0.

Common Pitfalls

• Same as LC 279. Precompute squares up to sqrt(n). O(n * sqrt(n)) DP. BFS gives same result.

Get Minimum Squares.java

Java

// Approach: DP. dp[n] = min perfect squares summing to n. dp[i] = min(dp[i - j*j] + 1) for all j*j <= i.
// Time: O(n * sqrt(n)) Space: O(n)
class Solution {
    public int minSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++)
            dp[i] = i;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                int sq = j * j;
                dp[i] = Math.min(dp[i], 1 + dp[i - sq]);
            }
        }

        return dp[n];
    }
}

Was this solution helpful?