Efficient Solution to Sum of Squares Problem in TypeScript

Optimizing Sum of Squares for a Given Positive Integer

Problem

Given a positive integer n, find the smallest number of squared integers which sum to n.

For example, given n = 13, return 2 since 13 = 32 + 22 = 9 + 4.

Given n = 27, return 3 since 27 = 32 + 32 + 32 = 9 + 9 + 9.

Problem Explanation

Given a positive integer n, our task is to find the smallest number of squared integers that sum up to n. This problem can be efficiently solved using a dynamic programming approach. We will build up the solution by solving smaller subproblems and using their solutions to construct the solution for larger problems.

Examples

For n = 13, the smallest number of squared integers is 2 (since 13 = 3² + 2² = 9 + 4).
For n = 27, the smallest number of squared integers is 3 (since 27 = 3² + 3² + 3² = 9 + 9 + 9).

Step-by-Step Solution

Understanding the Problem :

We need to find the minimum number of perfect square numbers (like 1, 4, 9, etc.) that sum up to the given integer n.

Dynamic Programming Approach :

We will use a dynamic programming array dp where dp[i] represents the smallest number of squared integers that sum up to i.
Initialize dp[0] to 0 since 0 can be represented by 0 numbers.
For each number from 1 to n, we will find the minimum number of squared integers that sum to that number by iterating over all possible squared integers that are less than or equal to the current number.

Algorithm :

Initialize an array dp of size n + 1 with all values set to infinity, except dp[0] which is 0.
For each number i from 1 to n, iterate through all possible squared integers j^2 (where j^2 <= i) and update dp[i] as dp[i] = min(dp[i], dp[i - j^2] + 1).

TypeScript Implementation :

function minSquares(n: number): number {
    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];
}

// Example usage:
console.log(minSquares(13)); // Output: 2
console.log(minSquares(27)); // Output: 3

Explanation of the Code:

Initialization :

We create an array dp of length n + 1 and initialize all values to infinity. The value at dp[0] is set to 0 because zero squared integers sum to 0.

Dynamic Programming Loop :

For each number i from 1 to n, we iterate through all perfect squares j^2 that are less than or equal to i.
For each perfect square j^2, we update dp[i] with the minimum value between dp[i] and dp[i - j^2] + 1.
The dp[i - j^2] + 1 represents the number of squared integers needed to sum to i, considering one more square j^2.

Alternative Solutions

Breadth-First Search (BFS):

Another approach is to use BFS where each node in the search tree represents a remaining value to be decomposed into squares. This method can be more intuitive but might not be as efficient as the dynamic programming approach.

Conclusion

Using dynamic programming provides an efficient way to solve the problem of finding the smallest number of squared integers that sum up to a given number n. The algorithm runs in O(n√n) time, making it suitable for large values of n.

“Optimizing code is like solving a puzzle — each piece you place perfectly brings you closer to the complete picture.” — Burhanuddin Mulla Hamzabhai

This solution provides a comprehensive approach to understanding and implementing the dynamic programming technique for this problem, ensuring an efficient and effective solution.

Burhanuddin’s Code Compendium

Thank you for being a part of the Burhanuddin’s Code Compendium community! Before you go:

Follow us: LinkedIn | YouTube| Newsletter
Listen to our podcast on: Spotify| Amazon Music | Apple Podcasts
More content at Burhanuddin’s Code Compendium