Perfect Squares

                                            
class Solution {
public:
    int numSquares(int n) {
        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] = min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
};

                                            
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[i - j * j] + 1);
            }
        }
        
        return dp[n];
    }
}

                                            
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = min(dp[i - j*j] + 1 for j in range(1, int(i**0.5) + 1))
        return dp[n]

                                            
int numSquares(int n) {
    while (n % 4 == 0)
        n /= 4;
    
    if (n % 8 == 7)
        return 4;
    
    for (int a = 0; a * a <= n; ++a) {
        int b = sqrt(n - a * a);
        if (a * a + b * b == n)
            return !!a + !!b;
    }
    
    return 3;
}

                                            
public class Solution {
    public int NumSquares(int n) {
        while (n % 4 == 0) {
            n /= 4;
        }
        if (n % 8 == 7) {
            return 4;
        }
        for (int a = 0; a * a <= n; a++) {
            int b = (int)Math.Sqrt(n - a * a);
            if (a * a + b * b == n) {
                return (a == 0 ? 0 : 1) + (b == 0 ? 0 : 1);
            }
        }
        return 3;
    }
}

                                            
/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    
    return dp[n];
};

                                            
function numSquares(n: number): number {
    const dp = new Array(n + 1).fill(Number.MAX_VALUE);
    dp[0] = 0;
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j*j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
        }
    }
    
    return dp[n];
};

                                            
class Solution {
    /**
     * @param Integer $n
     */
    function numSquares($n) {
        $dp = array_fill(0, $n + 1, PHP_INT_MAX);
        $dp[0] = 0;
        
        for ($i = 1; $i <= $n; $i++) {
            for ($j = 1; $j * $j <= $i; $j++) {
                $dp[$i] = min($dp[$i], $dp[$i - $j * $j] + 1);
            }
        }
        
        return $dp[$n];
    }
}

                                            
class Solution {
    func numSquares(_ n: Int) -> Int {
        var dp = Array(repeating: Int.max, count: n + 1)
        dp[0] = 0
        
        for i in 1...n {
            var j = 1
            while j * j <= i {
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
            }
        }
        
        return dp[n]
    }
}

                                            
class Solution {
    fun numSquares(n: Int): Int {
        val dp = IntArray(n + 1) { it }
        for (i in 1..n) {
            var j = 1
            while (j * j <= i) {
                dp[i] = minOf(dp[i], dp[i - j * j] + 1)
                j++
            }
        }
        return dp[n]
    }
}

                                            
class Solution {
  int numSquares(int n) {
    List<int> dp = List<int>.filled(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      int minVal = i;
      int j = 1;
      int square = 1;
      while (square <= i) {
        minVal = min(minVal, 1 + dp[i - square]);
        j++;
        square = j * j;
      }
      dp[i] = minVal;
    }
    return dp[n];
  }
}

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

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

                                            
# @param {Integer} n
# @return {Integer}
def num_squares(n)
    dp = Array.new(n + 1, n)
    dp[0] = 0
    
    (1..n).each do |i|
        (1..Math.sqrt(i).to_i).each do |j|
            dp[i] = [dp[i], dp[i - j * j] + 1].min
        end
    end
    
    return dp[n]
end

                                            
object Solution {
    def numSquares(n: Int): Int = {
        val dp = Array.fill(n + 1)(Int.MaxValue)
        dp(0) = 0
        
        for (i <- 1 to n) {
            var j = 1
            while (j * j <= i) {
                dp(i) = math.min(dp(i), dp(i - j * j) + 1)
                j += 1
            }
        }
        
        dp(n)
    }
}

                                            
impl Solution {
    pub fn num_squares(n: i32) -> i32 {
        let n = n as usize;
        let mut dp = vec![0; n + 1];
        for i in 1..=n {
            dp[i] = i;
            let mut j = 1;
            while j * j <= i {
                dp[i] = dp[i].min(dp[i - j * j] + 1);
                j += 1;
            }
        }
        dp[n] as i32
    }
}

To solve this coding challenge, we need to determine the least number of perfect square numbers that sum up to a given integer \( n \). The approach to solving this problem involves dynamic programming.

# Explanation

The core idea is to use dynamic programming (DP) to build a table where each position in the table indicates the minimum number of perfect square numbers that sum up to that index. Here are the detailed steps to approach this problem:

Understand Perfect Squares : A perfect square is an integer that can be represented as \( k^2 \) where \( k \) is an integer. For example, 1, 4, 9, and 16 are perfect squares.
Initialize a DP Array : Create an array
dp

where
dp[i]

will hold the minimum number of perfect squares that sum to
i

.
Base Case : Naturally,
dp[0]

is 0 because zero perfect squares sum to 0.
Fill the DP Array : Iterate from 1 to \( n \). For each index
i

, determine the minimum number of perfect squares that can sum to
i

by considering all valid squares \( j^2 \) such that \( j^2 \leq i \).

Detailed Steps in Pseudocode

Here's the detailed explanation broken down into a pseudocode representation:

Step 1: Initialize the DP Array

Create an array
dp

of size \( n + 1 \) and initialize all values to infinity, except for
dp[0]

which should be 0. This is because no squares are needed to sum to 0.

                                            
# Initialize dp array with size n+1
dp = array of size (n + 1)
# Set all dp values to infinity initially, except dp[0] which is 0
for i from 1 to n inclusive:
    dp[i] = infinity
dp[0] = 0

Step 2: Populate the DP Array

For each number \( i \) from 1 to \( n \):

Iterate over all perfect squares \( j^2 \) such that \( j^2 \leq i \).
Update
dp[i]

to be the minimum of its current value and
dp[i - j^2] + 1

.

                                            
# Fill the dp array
for i from 1 to n inclusive:
    j = 1
    while j*j <= i:
        # Update dp[i] as the minimum of its current value and dp[i - j^2] + 1
        dp[i] = minimum(dp[i], dp[i - j*j] + 1)
        # Increment j to check next perfect square
        j = j + 1

Step 3: Return the Result

The result will be stored in
dp[n]

, which will contain the least number of perfect square numbers summing up to
n

.

                                            
# Return the result stored in dp[n]
return dp[n]

By following these steps meticulously and filling the DP array accordingly, we can efficiently determine the least number of perfect squares that sum up to \( n \).

Example Walkthrough

Let's go through an example to understand better:

Example 1: \( n = 12 \)

Initialize
dp

array: \( \text{dp} = [0, \infty, \infty, \infty, \ldots, \infty] \)
Compute from
i = 1

to
12

:

For
i = 1

: Only
1^2

fits, so
dp[1]

= 1.
For
i = 2

: Only
1^2

fits, so
dp[2]

= 2.
For
i = 3

: Only
1^2

fits, so
dp[3]

= 3.
For
i = 4

: Both
1^2

and
2^2

fit, so
dp[4]

= 1 (i.e., \( 4 = 2^2 \)).
Continue this process up to
i = 12

, and determine
dp[12]

through similar steps.

The final value of

dp[12]

will be

3

, signifying that the least number of perfect squares summing to 12 is

3

(i.e., \( 4 + 4 + 4 \)).