grid47 Exploring patterns and algorithms
Oct 10, 2024
5 min read
Solution to LeetCode 279: Perfect Squares Problem
Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is a number that is the square of an integer. Your goal is to determine the minimum number of perfect squares that sum up to the given integer n.
Problem
Approach
Steps
Complexity
Input: You are given a positive integer n. Your task is to find the least number of perfect square numbers that sum up to n.
Example: Input: n = 15
Constraints:
• 1 <= n <= 10^4
Output: Return the least number of perfect square numbers that sum to n.
Example: Output: 4
Constraints:
• The returned number represents the minimum number of perfect squares that sum to n.
Goal: Minimize the number of perfect square numbers that sum up to n.
Steps:
• Step 1: Initialize an array `cnt` where `cnt[i]` represents the least number of perfect squares that sum to i.
• Step 2: Set `cnt[0] = 0` since no perfect squares are needed to sum to 0.
• Step 3: For each number `i` from 1 to n, try subtracting all perfect squares less than or equal to `i` and update the value of `cnt[i]` by taking the minimum value.
• Step 4: After iterating through all numbers, `cnt[n]` will store the least number of perfect square numbers that sum to n.
Goal: The goal is to find the least number of perfect squares that sum to the given integer n, ensuring that the solution is efficient.
Steps:
• The value of n can be as large as 10^4, so an efficient solution is required.
Assumptions:
• The input n is always a positive integer.
• Input: Input: n = 12
• Explanation: The least number of perfect square numbers that sum up to 12 is 3, since 12 = 4 + 4 + 4.
• Input: Input: n = 15
• Explanation: The least number of perfect square numbers that sum up to 15 is 4, since 15 = 9 + 4 + 1 + 1.
Approach: The approach uses dynamic programming to solve the problem by iterating over all integers up to n and finding the minimum number of perfect squares that sum to each integer.
Observations:
• The problem can be solved efficiently using dynamic programming by iterating over all numbers up to n and using the previous results to calculate the minimum for the current number.
• By using dynamic programming, we avoid redundant calculations, making the solution scalable for large values of n.
Steps:
• Step 1: Create an array `cnt` where `cnt[i]` will store the least number of perfect squares that sum to i.
• Step 2: Initialize `cnt[0] = 0` because no squares are needed for 0.
• Step 3: For each integer from 1 to n, find the minimum number of squares by checking all perfect squares less than or equal to the integer.
• Step 4: Once the array is populated, return the value of `cnt[n]`.
Empty Inputs:
• No empty input is expected as n is always greater than or equal to 1.
Large Inputs:
• For large values of n (e.g., up to 10^4), ensure that the dynamic programming approach efficiently calculates the solution.
Special Values:
• If n is a perfect square (e.g., 1, 4, 9), the answer is 1.
Constraints:
• The solution should handle inputs up to 10^4 efficiently, with an optimal time complexity.
Defines the function `numSquares`, which takes an integer `n` and returns the minimum number of perfect squares that sum up to `n`.
2 : Initialize DP Array
vector<long> cnt(n +1, INT_MAX);
Initializes a dynamic programming array `cnt` of size `n + 1` to store the minimum number of squares needed to sum up to each number. Initially, all values are set to `INT_MAX`, except `cnt[0]`.
3 : Base Case Initialization
cnt[0] =0;
Sets the base case `cnt[0] = 0`, as 0 requires 0 squares.
4 : Outer Loop - Iterate Through Numbers
for(int i =1; i <= n; i++)
Starts an outer loop to iterate through all numbers from 1 to `n`. Each `i` represents the target number to decompose into perfect squares.
5 : Inner Loop - Check Perfect Squares
for(int j =1; j * j <= i; j++)
Starts an inner loop to check all possible perfect squares `j * j` less than or equal to the current number `i`.
6 : Update DP Array
cnt[i] = min(cnt[i], cnt[i - j * j] +1);
Updates the value of `cnt[i]` by considering the current perfect square `j * j` and finding the minimum number of squares required by checking `cnt[i - j * j] + 1`.
7 : Return Result
return cnt[n];
Returns the minimum number of perfect squares needed to sum up to `n` from the `cnt` array.
Best Case: O(n * sqrt(n))
Average Case: O(n * sqrt(n))
Worst Case: O(n * sqrt(n))
Description: The time complexity is O(n * sqrt(n)) because we need to check each number from 1 to n and iterate over all perfect squares less than or equal to that number.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) as we use an array to store the minimum number of perfect squares for each number from 0 to n.
