Ways to Express an Integer as Sum of Powers
MedPrompt
Given two positive integers n and x.
Return the number of ways n can be expressed as the sum of the xth power of unique positive integers, in other words, the number of sets of unique integers [n1, n2, ..., nk] where n = n1x + n2x + ... + nkx.
Since the result can be very large, return it modulo 109 + 7.
For example, if n = 160 and x = 3, one way to express n is n = 23 + 33 + 53.
Example 1:
Input: n = 10, x = 2
Output: 1
Explanation: 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
Explanation: We can express n in the following ways:
- n = 41 = 4.
- n = 31 + 11 = 4.
Constraints:
1 <= n <= 3001 <= x <= 5
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a simple recursive function to explore all possible combinations of unique integer powers that could sum up to n. It tries including or excluding each possible power num^x and recursively calls itself for the remaining target sum. This method directly translates the problem's combinatorial nature into code but without any optimizations.
Algorithm
- Define a recursive function
countWays(target, num, x). - Base Case 1: If
targetis 0, a valid combination is found. Return 1. - Base Case 2: If
targetis negative, or ifnum^xis greater thantarget, this path is invalid. Return 0. - Recursive Step: Explore two choices for the current number
num:- Include
num^x: Recursively callcountWays(target - num^x, num + 1, x). - Exclude
num^x: Recursively callcountWays(target, num + 1, x).
- Include
- The result is the sum of the outcomes of these two choices, taken modulo
10^9 + 7. - The initial call is
countWays(n, 1, x).
Walkthrough
We define a recursive helper function, say countWays(target, num), where target is the remaining sum we need to achieve, and num is the current integer base we are considering. The function explores two possibilities for each num:
- Include
num^x: If we usenum^x, the new target becomestarget - num^x, and we move to the next integernum + 1to ensure uniqueness. - Exclude
num^x: If we don't usenum^x, the target remains the same, and we move tonum + 1.
The total number of ways is the sum of ways from these two choices. The recursion stops when a solution is found (target == 0), or when a path becomes invalid (target < 0 or num^x > target). The initial call is countWays(n, 1).
class Solution { int MOD = 1_000_000_007; public int numberOfWays(int n, int x) { return countWays(n, 1, x); } private int countWays(int target, int num, int x) { // Base case: A valid combination is found. if (target == 0) { return 1; } long power = 1; for (int i = 0; i < x; i++) power *= num; // Base case: Current number's power exceeds target, or target becomes negative. if (target < 0 || power > target) { return 0; } // Recursive step: // 1. Include the current number's power. int waysWith = countWays(target - (int) power, num + 1, x); // 2. Exclude the current number's power. int waysWithout = countWays(target, num + 1, x); return (waysWith + waysWithout) % MOD; }}Complexity
Time
O(2^k), where `k` is the number of candidate integers (`k <= n^(1/x)`). This is exponential and too slow for the given constraints.
Space
O(k), where `k` is the maximum possible base number such that `k^x <= n`. This space is used by the recursion stack. In the worst case (`x=1`), this is O(n).
Trade-offs
Pros
Simple to understand and implement.
Follows the problem definition very closely.
Cons
Extremely inefficient due to a large number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
This approach optimizes the brute-force recursion by using memoization to store the results of subproblems. By caching the results in a 2D array, we avoid re-calculating the number of ways for a given (target, num) state. This is a top-down dynamic programming approach that significantly improves performance.
Algorithm
- Create a memoization table
dp[n+1][k+1]initialized with a sentinel value (e.g.,nullor -1), wherekis the max base. - Define a recursive function
solve(target, num, x). - Base Cases: Same as the brute-force approach.
- Memoization Check: Before computing, check if
dp[target][num]has been calculated. If so, return the stored value. - Recursive Step: If not memoized, compute the result by summing the 'include' and 'exclude' options as in the brute-force approach.
- Store Result: Store the computed result in
dp[target][num]before returning. - The initial call is
solve(n, 1, x).
Walkthrough
This approach enhances the brute-force recursion by adding a memoization table (a 2D array dp) to store the results of subproblems. This technique is also known as top-down dynamic programming. The state is defined by (target, num), so dp[target][num] stores the result for countWays(target, num). Before any computation, the function checks the dp table. If a result exists, it's returned immediately. Otherwise, the result is computed, stored in the table, and then returned. This prevents re-computation of the same state, drastically improving efficiency.
class Solution { int MOD = 1_000_000_007; Integer[][] dp; public int numberOfWays(int n, int x) { // dp[i][j] will store the number of ways to get sum 'i' using numbers from 'j' onwards. dp = new Integer[n + 1][n + 1]; return solve(n, 1, x); } private int solve(int target, int num, int x) { if (target == 0) { return 1; } long power = power(num, x); if (num > n || target < 0 || power > target) { return 0; } if (dp[target][num] != null) { return dp[target][num]; } // Option 1: Include num^x int include = solve(target - (int)power, num + 1, x); // Option 2: Exclude num^x int exclude = solve(target, num + 1, x); dp[target][num] = (include + exclude) % MOD; return dp[target][num]; } // Custom power function to avoid double precision issues and handle overflow private long power(int base, int exp) { long res = 1; for (int i = 0; i < exp; i++) { res *= base; if (res > 301) return 301; // Cap at n+1, since n <= 300 } return res; }}Complexity
Time
O(n * k), where `k` is the number of candidate integers (`k <= n^(1/x)`). Each state `(target, num)` is computed only once.
Space
O(n * k), where `k <= n^(1/x)`. This is for the memoization table. The recursion stack adds an additional O(k) space.
Trade-offs
Pros
Drastically reduces time complexity compared to brute-force, making it efficient enough for the given constraints.
Maintains a logical structure that is similar to the pure recursive solution.
Cons
Uses more space than the iterative bottom-up DP approach due to the 2D memoization table and the recursion stack.
Can lead to a stack overflow error for very deep recursion, though not an issue with the given constraints.
This is a bottom-up dynamic programming approach that iteratively builds the solution. It's analogous to the 0/1 Knapsack problem and is generally the most efficient method in terms of both time and space. We use a 1D array to keep track of the number of ways to form each sum from 0 to n.
Algorithm
- Create a 1D DP array
dpof sizen + 1and initialize all elements to 0. - Set
dp[0] = 1, as there is one way to make a sum of 0 (by choosing no numbers). - Iterate through each possible base number
numfrom 1 upwards. - For each
num, calculate its powerp = num^x. Ifp > n, stop. - For each
p, iteratejfromndown top. - Update
dp[j]using the formula:dp[j] = (dp[j] + dp[j - p]) % MOD. - The downward iteration of
jensures that each powerpis used at most once for any sum. - The final answer is
dp[n].
Walkthrough
This approach uses bottom-up dynamic programming, which is an iterative way to solve the problem. It's conceptually similar to the 0/1 Knapsack problem. We use a 1D array dp of size n+1, where dp[i] stores the number of ways to form the sum i. We initialize dp[0] = 1 (one way to make a sum of 0: using no numbers). Then, we iterate through each possible number we can use, which are 1^x, 2^x, 3^x, ... as long as the power is less than or equal to n. For each power p = num^x, we update the dp array. We iterate from j = n down to p. The update rule is dp[j] = (dp[j] + dp[j - p]). The downward loop for j is critical; it ensures that each power p is used at most once in any given sum, fulfilling the 'unique integers' requirement. The final answer is dp[n].
class Solution { public int numberOfWays(int n, int x) { int MOD = 1_000_000_007; int[] dp = new int[n + 1]; dp[0] = 1; // Iterate through each number 'num' whose x-th power could be part of the sum. for (int num = 1; ; num++) { long powerVal = 1; // Calculate num^x safely, checking for overflow against n. for (int i = 0; i < x; i++) { powerVal *= num; if (powerVal > n) break; } if (powerVal > n) { break; // All subsequent numbers will also have powers > n. } int power = (int) powerVal; // Iterate downwards to ensure each number's power is used at most once (0/1 knapsack style). for (int j = n; j >= power; j--) { dp[j] = (dp[j] + dp[j - power]) % MOD; } } return dp[n]; }}Complexity
Time
O(n * k), where `k` is the number of candidate integers (`k <= n^(1/x)`). This is asymptotically the same as the memoized approach.
Space
O(n), for the 1D DP array. This is the most space-efficient approach.
Trade-offs
Pros
Most efficient in terms of space complexity.
Avoids recursion overhead, which can lead to slightly better constant-factor performance than the memoized version.
Iterative nature prevents any risk of stack overflow.
Cons
The logic, especially the downward iteration for the inner loop, can be less intuitive to grasp compared to the recursive formulation.
Solutions
Solution
class Solution {public int numberOfWays(int n, int x) { final int mod = (int)1 e9 + 7; int[][] f = new int[n + 1][n + 1]; f[0][0] = 1; for (int i = 1; i <= n; ++i) { long k = (long)Math.pow(i, x); for (int j = 0; j <= n; ++j) { f[i][j] = f[i - 1][j]; if (k <= j) { f[i][j] = (f[i][j] + f[i - 1][j - (int)k]) % mod; } } } return f[n][n]; }}class Solution {public: int numberOfWays(int n, int x) { const int mod = 1e9 + 7; int f[n + 1][n + 1]; memset(f, 0, sizeof(f)); f[0][0] = 1; for (int i = 1; i <= n; ++i) { long long k = (long long)pow(i, x); for (int j = 0; j <= n; ++j) { 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]; }};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]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.