algoadvance

Leetcode 279. Perfect Squares

Problem Statement

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 8 are not.

Example

Clarifying Questions

  1. Input Range: What is the range of the input integer n?
    • Typical constraint on the problem can be assumed as 1 <= n <= 10^4.
  2. Allowed Time Complexity: Is there any guideline for the expected time complexity to solve the problem?
    • This problem typically expects a Polynomial or better complexity, dynamic programming solution with O(n √n) complexity is common.
  3. Output: What should the function return if n is already a perfect square?
    • If n is a perfect square, it should return 1 because only one perfect square is needed to sum to n.

Strategy

We will use Dynamic Programming (DP) to solve this problem. The idea is to build a DP table where dp[i] represents the minimum number of perfect squares summing to i.

Steps:

  1. Initialization: Initialize dp[0] to 0 because 0 perfect squares sum up to 0. Initialize other positions dp[1] to dp[n] to infinity (INT_MAX) as they are to be computed.

  2. Iterations: For each number from 1 to n, we check all smaller perfect squares (e.g., 1, 4, 9, …) and update our dp array based on previous results.

  3. Transition Relation: For a given i, the value of dp[i] can be derived from the minimum value of dp[i - j*j] + 1 for each perfect square j*j less than or equal to i.

  4. Final Output: The final value dp[n] will be our answer.

Code

Let’s implement this strategy in C++:

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

using namespace std;

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;  // Base case: 0 numbers to sum to 0
        
        // Precompute the square numbers
        vector<int> squares;
        for (int i = 1; i * i <= n; ++i) {
            squares.push_back(i * i);
        }
        
        // Fill the DP table
        for (int i = 1; i <= n; ++i) {
            for (int square : squares) {
                if (i - square >= 0) {
                    dp[i] = min(dp[i], dp[i - square] + 1);
                } else {
                    break;  // No need to check further as squares are sorted
                }
            }
        }
        
        return dp[n];
    }
};

Time Complexity

This solution guarantees that the problem is solved efficiently within the typical constraints for n.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI