Perfect Squares

Problem Statement

In this problem, you are tasked with determining the minimum count of perfect square numbers which, when summed, equate to a given integer n. A perfect square is defined as an integer that can be expressed as the product of some integer with itself. Examples of perfect squares include the numbers 1, 4, 9, 16, and so forth, while examples of non-perfect squares are 3 and 11.

The challenge lies in efficiently determining the smallest combination of these perfect squares that sums up to the integer n.

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 <= 104

Approach and Intuition

The task can be tackled by understanding and applying the principles of dynamic programming. The main idea is to construct solutions to smaller subproblems and use these solutions in a bottom-up manner to solve the larger problem at hand.

1. Initialize an array dp of size n + 1 with a default value of a large number (like float('inf')) that signifies an undefined or infinite distance. This array will hold the minimum number of perfect squares needed for each integer from 0 to n. Set dp[0] = 0 because zero perfect squares sum up to zero.
2. Loop through each number i from 1 to n. For each number, iterate through each perfect square j starting from 1 until j^2 <= i.
   • For each perfect square j, compute the potential new count as dp[i - j^2] + 1 - this represents the total number of perfect squares used if we include j^2 in the sum that makes up i.
   • If this new calculated value is smaller than the currently stored dp[i], update dp[i] with the new smaller value. This ensures that the minimum count is always stored.
3. By the end of this process, dp[n] will contain the minimum number of perfect square numbers required to sum up to n.

This dynamic programming approach ensures that all possibilities are considered without repetitive calculations, making the solution efficient and scalable within the problem's constraints.

Solutions

class Solution {

  protected boolean checkPerfectSquare(int num) {
    int sqrt = (int) Math.sqrt(num);
    return num == sqrt * sqrt;
  }

  public int countSquares(int number) {
    while (number % 4 == 0)
      number /= 4;
    if (number % 8 == 7)
      return 4;

    if (this.checkPerfectSquare(number))
      return 1;

    for (int i = 1; i * i <= number; ++i) {
      if (this.checkPerfectSquare(number - i * i))
        return 2;
    }

    return 3;
  }
}