Perfect Squares

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazonMicrosoftMeta

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

Examples

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⁴

State Transition

Let dp[i] be the minimum number of perfect squares that sum to i. To form a sum of i, the last perfect square we add can be any j² such that j² ≤ i. Thus: dp[i] = 1 + min(dp[i - j²]) for all j where j * j ≤ i.

Initialize dp[0] = 0 (0 squares are needed to sum to 0), and all other dp[i] = i (worst case: all 1s).

Solution 1: 1D DP

import java.util.*;

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

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

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1

        return dp[n]

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int numSquares(int n) {
        std::vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = std::min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
};

Complexity Analysis:

Time Complexity: O(N * √N). For each index i up to n, the inner loop runs √i times.
Space Complexity: O(N) to store the DP array.

Solution 2: Legendre’s Three-Square Theorem (O(√N) Math)

By Lagrange’s four-square theorem, every natural number can be represented as the sum of four integer squares. By Legendre’s three-square theorem, a natural number can be represented as the sum of three squares if and only if it is not of the form n = 4ᵃ(8b + 7) for integers a and b.

Thus, the answer can only be 1, 2, 3, or 4:

Answer is 1: if n is a perfect square.
Answer is 4: if n can be written as 4ᵃ(8b + 7).
Answer is 2: if n = i² + j² (check by trying all values of i from 1 to √n and checking if n - i² is a perfect square).
Answer is 3: if none of the above are true.

class Solution {
    private boolean isSquare(int n) {
        int sqrt = (int) Math.sqrt(n);
        return sqrt * sqrt == n;
    }

    public int numSquares(int n) {
        if (isSquare(n)) return 1;

        // Legendre's condition: if n = 4^a * (8b + 7), answer is 4
        int temp = n;
        while (temp % 4 == 0) {
            temp /= 4;
        }
        if (temp % 8 == 7) return 4;

        // Check if it can be represented as the sum of two squares
        for (int i = 1; i * i <= n; i++) {
            if (isSquare(n - i * i)) return 2;
        }

        return 3;
    }
}

import math

class Solution:
    def numSquares(self, n: int) -> int:
        def is_square(x: int) -> bool:
            sqrt = int(math.isqrt(x))
            return sqrt * sqrt == x

        if is_square(n):
            return 1

        # Legendre's condition: if n = 4^a * (8b + 7), answer is 4
        temp = n
        while temp % 4 == 0:
            temp //= 4
        if temp % 8 == 7:
            return 4

        # Check if sum of two squares
        i = 1
        while i * i <= n:
            if is_square(n - i * i):
                return 2
            i += 1

        return 3

#include <cmath>

class Solution {
    bool isSquare(int n) {
        int sqrt_val = std::sqrt(n);
        return sqrt_val * sqrt_val == n;
    }

public:
    int numSquares(int n) {
        if (isSquare(n)) return 1;

        int temp = n;
        while (temp % 4 == 0) {
            temp /= 4;
        }
        if (temp % 8 == 7) return 4;

        for (int i = 1; i * i <= n; i++) {
            if (isSquare(n - i * i)) return 2;
        }

        return 3;
    }
};