2787. Ways to Express an Integer as Sum of Powers


Problem Description

The objective of this problem is to find the total number of unique ways we can represent a given positive integer n as a sum of the xth powers of distinct positive integers. In other words, for two positive numbers n and x, we need to figure out in how many different ways we can find sets of unique positive integers [n1, n2, ..., nk] such that when each number ni is raised to the power of x and then all of these xth powers are added together, the sum equals n. The final result must be returned modulo 10^9 + 7 to manage large numbers.

For a given number n = 160 and x = 3, an example of such a representation is 160 = 2^3 + 3^3 + 5^3. However, the problem asks for the count of all possible such representations, not just one.

Intuition

The intuition behind the solution is to use dynamic programming to keep track of the number of ways we can form different sums using xth powers of numbers up to i. We define a 2-dimensional array f where f[i][j] will store the number of ways we can form the sum j using the xth power of integers from 1 to i.

To populate this array, we'll start with the understanding that there's exactly one way to achieve a sum of 0 (by using no numbers), so f[0][0] = 1. Then, we iterate over each number from 1 to n, calculating its xth power (k = pow(i, x)) and updating the f array. For each i, we iterate through all possible sums j from 0 to n, and we do the following:

  • We first set f[i][j] to f[i-1][j], which represents the number of ways to get a sum j without using the ith number.
  • If k (the xth power of i) is less than or equal to j, it means we can include i in a sum that totals j. Therefore, we add the number of ways to get the remaining sum (j - k) using integers up to i - 1. That is, f[i][j] += f[i-1][j - k].
  • Every time we update f[i][j], we take the result modulo 10^9 + 7 to keep the number within bounds.

At the end of the iterations, f[n][n] will hold the total number of ways we can represent n using the xth powers of unique integers, and this is what we return.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

How many times is a tree node visited in a depth first search?

Solution Approach

The solution uses dynamic programming, a method often used to solve problems that involve counting combinations or ways of doing something. To tackle this particular problem, we create a two-dimensional list f that serves as our DP table. This table has dimensions (n+1) x (n+1) where n is the input integer whose expressions we need to find.

The idea is to gradually build up the number of ways to reach a certain sum j using xth powers of numbers up to i. Let's take a closer look at how the code implements this:

  • We start by initializing our DP table, f, with zeros and setting f[0][0] to 1, as there's only one way to have a sum of 0 (using none of the numbers).

    1f = [[0] * (n + 1) for _ in range(n + 1)]
    2f[0][0] = 1
  • We then iterate through each number i from 1 to n, since we are considering sums of numbers raised to the power x. And for each number, we calculate its xth power and store it in k.

    1for i in range(1, n + 1):
    2    k = pow(i, x)
  • For each i, we then go through all possible sums j. We set f[i][j] to the number of ways to form the same sum j without using i. This is obtained from f[i - 1][j].

    1for j in range(n + 1):
    2    f[i][j] = f[i - 1][j]
  • If the xth power of i (k) is less than or equal to j, we find the number of ways to make up the remaining value (j - k) with the previous numbers. We then add this count to our current count of ways for sum j.

    1if k <= j:
    2    f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod
  • The % mod ensures that the resulting count is within the bounds set by the problem statement.

By the end of these iterations, f[n][n] contains the desired count of ways to express n as a sum of the xth power of unique positive integers. Because we iterated over all numbers from 1 to n and for each considered all subsets of these numbers and ways to sum up to j, our final count is comprehensive.

Finally, the solution function returns this count:

1return f[n][n]

By systematically adding the ways to form smaller sums and building up to the larger sums, the dynamic programming approach eliminates redundant calculations, thus optimizing the process of finding all possible combinations that sum up to n using powers of x.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example Walkthrough

Let's take a small example to illustrate the solution approach. Consider n = 10 and x = 2. We want to find out how many unique ways can we express n as a sum of squares of distinct positive integers.

  1. Initialize the two-dimensional list, f, with zeros and set f[0][0] to 1. This represents the number of ways to represent 0 as the sum of squares of numbers from 0. There is only one way, which is to use none of the numbers:

    1f = [
    2    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    3    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    4    ... (up to f[10][0] which are all zeros)
    5]
  2. We iterate through numbers i from 1 to n (1 to 10), and for each number, we compute its square (k = i^2).

    Example for i = 1: k = 1^2 = 1

  3. With k = 1 for i = 1, we iterate through sums j from 0 to n. If k (1 in this case) is less than or equal to j, we add the count for j-k from the previous iterations. This represents including number i in our sum.

    Example updates for i = 1 and j = 1 to 10 (with modulo operation omitted for simplicity):

    1f[1][1] = f[0][1] + f[0][0] = 1 (only using 1^2)
    2f[1][2] = f[0][2] + f[0][1] = 0 (can't express 2 as only square of 1)
    3...
    4f[1][10] = f[0][10] + f[0][9] = 0 (can't express 10 as only square of 1)
  4. We repeat step 3 for all i up to n. For instance, when i = 2, k = 2^2 = 4.

    Example updates for i = 2:

    1f[2][4] = f[1][4] + f[1][0] = 1 (using 2^2)
    2f[2][5] = f[1][5] + f[1][1] = 1 (using 1^2 and 2^2)
    3...
    4f[2][10] = f[1][10] + f[1][6] = 1 (using 1^2 and 3^2)
  5. As we continue this process and update f for increasing i and j, we eventually build up the count. By the time we reach f[10][10], it will have been updated with all possible ways to express 10 as a sum of squares of unique integers from 1 to 3, as 4^2 already exceeds 10, and higher powers won't be considered.

After evaluating f[i][j] with the above steps while including the necessary modulo operation, the answer for f[10][10] will give us the total number of ways we can represent 10 using the squares of unique integers. In this case, the unique ways are {1^2, 3^2} and {1^2, 2^2, 3^2} minus {2^2, 3^2} since 2^2 + 3^2 is greater than 10, giving us a final answer as 2.

Solution Implementation

1class Solution:
2    def numberOfWays(self, total_sum: int, exponent: int) -> int:
3        # Modulo constant to prevent overflow issues for large numbers
4        MOD = 10 ** 9 + 7
5      
6        # Initializing a dynamic programming table where
7        # dp[i][j] represents the number of ways to write j as a sum
8        # of i-th powers of first i natural numbers.
9        dp = [[0] * (total_sum + 1) for _ in range(total_sum + 1)]
10      
11        # There is one way to form the sum 0 using 0 numbers: use no numbers at all.
12        dp[0][0] = 1
13      
14        # Iterate over all numbers from 1 to total_sum
15        for i in range(1, total_sum + 1):
16            # Calculate the i-th power of the number
17            power = pow(i, exponent)
18            # Iterate over all possible sums from 0 to total_sum
19            for j in range(total_sum + 1):
20                # The number of ways to form the sum j without using the i-th number
21                dp[i][j] = dp[i - 1][j]
22                # If the power is less than or equal to the sum j, then
23                # add the number of ways to form the previous sum j-power
24                if power <= j:
25                    dp[i][j] = (dp[i][j] + dp[i - 1][j - power]) % MOD
26      
27        # Return the number of ways to write total_sum as a sum of
28        # powers of the first total_sum natural numbers.
29        return dp[total_sum][total_sum]
30
1class Solution {
2
3    /**
4     * This method calculates the number of ways to reach a target sum `n`
5     * using unique powers `x` of the numbers from 1 to `n` inclusive.
6     * 
7     * @param n The target sum we want to achieve.
8     * @param x The power to which we will raise numbers.
9     * @return The number of ways to achieve the target sum using the powers.
10     */
11    public int numberOfWays(int n, int x) {
12        // Define the modulo constant to prevent overflow issues
13        final int MOD = (int) 1e9 + 7;
14
15        // Initialize a 2D array to store intermediate results
16        // f[i][j] will store the number of ways to reach the sum `j`
17        // using powers of numbers from 1 to `i`
18        int[][] dp = new int[n + 1][n + 1];
19
20        // There is exactly one way to reach the sum 0, which is by using no numbers
21        dp[0][0] = 1;
22
23        // Loop over every number up to `n` to compute the powers and the ways to reach each sum `j`
24        for (int i = 1; i <= n; ++i) {
25            // Calculate the power of the current number `i`
26            long power = (long) Math.pow(i, x);
27
28            // Loop over all sums from 0 to `n`
29            for (int j = 0; j <= n; ++j) {
30                // Initialize dp[i][j] with the number of ways to reach the sum `j` without using the current number
31                dp[i][j] = dp[i - 1][j];
32
33                // If adding the current power does not exceed the sum `j` (it's a valid choice to reach the sum `j`)
34                if (power <= j) {
35                    // Update the number of ways by adding the ways to reach the reduced sum `j - power`
36                    // and take modulo to handle large numbers
37                    dp[i][j] = (dp[i][j] + dp[i - 1][j - (int) power]) % MOD;
38                }
39            }
40        }
41
42        // Return the number of ways to reach the sum `n` using all numbers from 1 to `n` raised to the power `x`
43        return dp[n][n];
44    }
45}
46
1#include <vector>
2#include <cmath>
3#include <cstring>
4
5class Solution {
6public:
7    int numberOfWays(int n, int x) {
8        const int MOD = 1e9 + 7;                                // Modular constant for large numbers
9        std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0)); // DP table to store intermediate results
10
11        dp[0][0] = 1;                                          // Base case: one way to sum up 0 using 0 elements
12        for (int i = 1; i <= n; ++i) {                         // Loop through numbers from 1 to n
13            long long powerOfI = (long long)std::pow(i, x);    // Calculate the i-th power of x
14            for (int j = 0; j <= n; ++j) {                     // Loop through all the possible sums from 0 to n
15                dp[i][j] = dp[i - 1][j];                       // Without the current number i, ways are from previous
16                if (powerOfI <= j) {
17                    // If current power of i fits into sum j, add ways where i contributes to sum j
18                    dp[i][j] = (dp[i][j] + dp[i - 1][j - powerOfI]) % MOD;
19                }
20            }
21        }
22        return dp[n][n]; // Return the number of ways to get sum n using numbers 1 to n to the power of x
23    }
24};
25
1function numberOfWays(n: number, x: number): number {
2    // Modulo constant for the result as we only need the remainder
3    // after dividing by this large prime.
4    const MODULO = 10 ** 9 + 7;
5
6    // Creating a 2D array 'ways' of dimensions (n+1)x(n+1) to store
7    // the number of ways to write numbers as the sum of powers of x.
8    const ways = Array.from({ length: n + 1 }, () => 
9                  Array(n + 1).fill(0));
10
11    // Base case: there is only one way to write 0 - as an empty sum.
12    ways[0][0] = 1;
13
14    // Iterate over each number from 1 to n.
15    for (let i = 1; i <= n; ++i) {
16      
17        // Calculate the current power of i.
18        const power = Math.pow(i, x);
19
20        // Iterate over all the numbers from 0 to n to find the number
21        // of ways to write each number j as a sum of powers of integers.
22        for (let j = 0; j <= n; ++j) {
23
24            // The number of ways to write j without using i.
25            ways[i][j] = ways[i - 1][j];
26
27            // If current power does not exceed j, we can use it in the sum.
28            // We add the number of ways to write the remaining part
29            // (j - power) with numbers up to (i - 1).
30            if (power <= j) {
31                ways[i][j] = (ways[i][j] + ways[i - 1][j - power]) % MODULO;
32            }
33        }
34    }
35
36    // The answer is the number of ways to write n
37    // using powers of all numbers up to n.
38    return ways[n][n];
39}
40
Not Sure What to Study? Take the 2-min Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

The given Python code defines a function numberOfWays that calculates the number of ways to reach a total sum n by adding powers of integers up to n, each raised to the power of x. Below is an analysis of the code's time and space complexity:

Time Complexity

The algorithm consists of a nested loop where the outer loop runs n times, and the inner loop also runs n times. In every iteration of the inner loop, the algorithm performs constant-time operations, except for the pow(i, x) calculation, which is done once per outer loop iteration.

The pow function is typically implemented with a logarithmic time complexity concerning the exponent. However, since the exponent x is constant for the entire run of the algorithm, each call to pow will have a constant time complexity. Thus, we can consider the pow(i, x) part to have a time complexity of O(1) for each iteration of i.

Hence, the time complexity is primarily governed by the nested loop, resulting in a time complexity of O(n^2).

Space Complexity

The code uses a 2-dimensional list f with dimensions n + 1 by n + 1, which stores the computed values. This list is the primary consumer of memory in the algorithm.

The space complexity for the list f is O(n^2), which reflects the amount of memory used with respect to the input size n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫