#2787

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Ways to Express an Integer as Sum of Powers

Compute the number of ways to express an integer as a sum of unique powers using state transition dynamic programming efficiently.

dynamic programming

Problem Statement

Given two positive integers n and x, determine the total number of ways n can be expressed as the sum of unique positive integers each raised to the xth power. Each integer can be used at most once, and the order of integers does not matter.

Return the number of such combinations modulo 10^9 + 7. For example, with n = 10 and x = 2, there is exactly one way since 10 = 3^2 + 1^2, illustrating the need to consider unique powers carefully.

Examples

Example 1

Input: n = 10, x = 2

Output: 1

We can express n as the following: n = 32 + 12 = 10. It can be shown that it is the only way to express 10 as the sum of the 2nd power of unique integers.

Example 2

Input: n = 4, x = 1

Output: 2

We can express n in the following ways:

n = 41 = 4.
n = 31 + 11 = 4.

Constraints

1 <= n <= 300
1 <= x <= 5

Solution Approach

Define DP State

Use dp[k] to represent the number of ways to express k as the sum of xth powers of unique integers. Initialize dp[0] = 1 as the base case.

State Transition

Iterate over each integer i where i^x <= n and update dp[k] from high to low: dp[k] += dp[k - i^x] modulo 10^9 + 7. This ensures each integer is used at most once.

Return Result

After processing all integers, dp[n] holds the total number of valid combinations. This directly gives the answer required by the problem.

Complexity Analysis

Metric	Value
Time	O(n\sqrt[x]{n})
Space	O(n)

Time complexity is O(n * n^(1/x)) due to iterating all possible integers whose xth power is <= n and updating dp. Space complexity is O(n) since only a one-dimensional DP array is needed.

What Interviewers Usually Probe

Focus on unique usage of integers to avoid overcounting in the DP table.
Emphasize proper iteration order for state transitions to ensure correctness.
Clarify handling of modulo arithmetic to prevent integer overflow.

Common Pitfalls or Variants

Common pitfalls

Using integers multiple times instead of enforcing uniqueness.
Iterating dp array from low to high, which breaks the uniqueness constraint.
Failing to apply modulo 10^9 + 7 correctly in each update step.

Follow-up variants

Count combinations allowing repeated integers (classic coin change variant).
Compute the number of ways to express n as sum of factorials instead of powers.
Extend the problem to find all actual sets, not just the count.

FAQ

What pattern does this problem follow in dynamic programming?

It follows state transition dynamic programming, where each state represents the number of ways to reach a sum with unique xth powers.

Why must the DP array be updated from high to low?

Updating from high to low ensures each integer is counted at most once, preserving uniqueness in combinations.

How does modulo 10^9 + 7 affect the solution?

All additions are done modulo 10^9 + 7 to prevent integer overflow and match problem constraints.

Can this method handle n = 300 and x = 5 efficiently?

Yes, because the DP array scales linearly with n and only considers integers whose xth powers are <= n.

How do I extend this solution to find the actual sets?

You can modify the DP table to store lists of combinations, but this increases memory and complexity significantly.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the number of ways to select some numbers from the first $i$ positive integers such that the sum of their $x$-th powers equals $j$. Initially, $f[0][0] = 1$, and all others are $0$. The answer is $f[n][n]$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        mod = 10**9 + 7
        f = [[0] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for i in range(1, n + 1):
            k = pow(i, x)
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if k <= j:
                    f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod
        return f[n][n]

Continue Practicing

#2786 visit array positions to maximize score #2791 count paths that can form a palindrome in a tree #2801 count stepping numbers in range