Ways to Express an Integer as Sum of Powers solution and explanation
Google
9 more videos on this problem
Ways to Express an Integer as Sum of Powers | Recursion Memo | Leetcode 2787 | codestorywithMIKcodestorywithMIK · 21:20 · 8K views
Ways to Express an Integer as Sum of Powers | Leetcode 2787 | Memoization | TabulationTechdose · 35:48 · 2K views
2787. Ways to Express an Integer as Sum of Powers | Leetcode Biweekly 109codingMohan · 20:05 · 1K views
2787. Ways to Express an Integer as Sum of Powers | Leetcode Daily - PythonLeetcode Daily · 6:50 · 819 views
Daily Leetcode #1960: Aug 12, 2025 - 2787. Ways to Express an Integer as Sum of PowersProgramming Live with Larry · 10:08 · 775 views
2787. Ways to Express an Integer as Sum of Powers (Leetcode Medium)Programming Live with Larry · 7:31 · 614 views
Leetcode 2787. Ways to Express an Integer as Sum of Powers | DP with Memoization | Python SolutionStatLearn Tech · 15:27 · 603 views
Ways to Express an Integer as Sum of Powers | LeetCode 2787 - Python (3 Solutions)impoldev · 21:30 · 421 views
Master Dynamic Programming with Python - LeetCode 2787. Ways to Express an Integer as Sum of PowersvanAmsen · 7:14 · 317 views
Ways to Express an Integer as Sum of Powers | LeetCode 2787 | Recursive Thinking | DPCode Harmony · 29:57 · 257 views
The problem
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
Approach overview
Problem Overview: Given integers n and x, count how many ways you can represent n as a sum of unique integers where each number is raised to the power x. Each base integer can be used at most once, so the task becomes selecting distinct values i such that i^x adds up exactly to n.
Approach 1: Recursive Search with Memoization (Time: O(n * k), Space: O(n * k))
First compute all possible powers i^x where i^x ≤ n. Let k = floor(n^(1/x)). The recursion explores two choices for each base number: include the current power in the sum or skip it. The recursive state becomes (index, remaining), where index refers to the current base and remaining is the leftover value needed to reach n. Memoization stores results for previously computed states, avoiding repeated exploration of the same subproblems. This turns the exponential brute-force search into a manageable dynamic programming problem and is usually the easiest implementation during interviews. The technique combines recursion with dynamic programming style caching.
Approach 2: Dynamic Programming Table (Time: O(n * k), Space: O(n * k))
This approach converts the recursive decision process into a bottom-up DP table similar to a 0/1 knapsack count problem. Precompute all values i^x up to n. Define dp[i][s] as the number of ways to form sum s using the first i power values. For each power, you either exclude it (dp[i-1][s]) or include it if s ≥ power[i] (dp[i-1][s - power[i]]). Fill the table iteratively until reaching dp[k][n]. This version avoids recursion depth and is easier to reason about for engineers comfortable with classic DP transitions. The structure closely mirrors subset-sum counting.
Recommended for interviews: The memoized recursion is usually the fastest to implement and clearly communicates the include/exclude decision process. Interviewers often expect recognition that the problem reduces to a 0/1 subset-style dynamic programming problem over the values i^x. Showing the recursive solution first demonstrates problem decomposition, while the DP table version demonstrates stronger mastery of bottom-up optimization.
Approach 1: Recursive Approach with Memoization
This approach utilizes recursion to explore all possible combinations of unique integers whose x-th powers sum up to n. To improve its efficiency, we apply memoization to cache the results of state computations and avoid redundant calculations.
def numOfWays(n, x):
MOD = 1000000007
dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
def ways(n, x, idx):
if n == 0:
return 1
if n < 0 or idx <= 0:
return 0
if dp[n][idx] != -1:
return dp[n][idx]
res = ways(n, x, idx - 1)
if pow(idx, x) <= n:
res = (res + ways(n - pow(idx, x), x, idx - 1)) % MOD
dp[n][idx] = res
return res
return ways(n, x, n)
n = 10
x = 2
print(numOfWays(n, x))import java.util.Arrays;
public class WaysSumPowers {
static final int MOD = 1000000007;
int[][] dp;
public int numOfWays(int n, int x) {
dp = new int[n + 1][n + 1];
for (int[] row : dp) Arrays.fill(row, -1);
return countWays(n, x, n);
}
private int countWays(int n, int x, int current) {
if (n == 0) return 1;
if (n < 0 || current <= 0) return 0;
if (dp[n][current] != -1) return dp[n][current];
long powValue = (long) Math.pow(current, x);
int res = countWays(n, x, current - 1);
if (powValue <= n) {
res = (res + countWays((int) (n - powValue), x, current - 1)) % MOD;
}
dp[n][current] = res;
return res;
}
public static void main(String[] args) {
WaysSumPowers wsp = new WaysSumPowers();
System.out.println(wsp.numOfWays(10, 2));
}
}#include <iostream>
#include <vector>
#include <cmath>
#define MOD 1000000007
using namespace std;
int ways(int n, int x, int idx, vector<vector<int>>& dp) {
if (n == 0) return 1;
if (n < 0 || idx <= 0) return 0;
if (dp[n][idx] != -1) return dp[n][idx];
int res = ways(n, x, idx - 1, dp);
if (pow(idx, x) <= n) {
res = (res + ways(n - pow(idx, x), x, idx - 1, dp)) % MOD;
}
return dp[n][idx] = res;
}
int numOfWays(int n, int x) {
vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
return ways(n, x, n, dp);
}
int main() {
int n = 10, x = 2;
cout << numOfWays(n, x) << endl;
return 0;
}const numOfWays = function(n, x) {
const MOD = 1000000007;
const dp = Array.from({length: n + 1}, () => Array(n + 1).fill(-1));
const ways = function(n, x, idx) {
if (n === 0) return 1;
if (n < 0 || idx <= 0) return 0;
if (dp[n][idx] !== -1) return dp[n][idx];
let res = ways(n, x, idx - 1);
if (Math.pow(idx, x) <= n) {
res = (res + ways(n - Math.pow(idx, x), x, idx - 1)) % MOD;
}
dp[n][idx] = res;
return res;
};
return ways(n, x, n);
};
console.log(numOfWays(10, 2));#include <stdio.h>
#include <string.h>
#define MODULO 1000000007
int dp[301][301];
int countWays(int current, int power, int target, int next) {
if (target == 0) return 1;
if (target < 0 || next <= 0) return 0;
if (dp[target][next] != -1) return dp[target][next];
int take = countWays(current, power, target - (int)pow(current, power), next - 1);
int leave = countWays(current + 1, power, target, next - 1);
return dp[target][next] = (take + leave) % MODULO;
}
int main() {
int n = 10, x = 2;
memset(dp, -1, sizeof(dp));
printf("%d\n", countWays(1, x, n, n));
return 0;
}using System;
class Solution {
private const int MOD = 1000000007;
private int[,] dp;
public int NumOfWays(int n, int x) {
dp = new int[n + 1, n + 1];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
dp[i, j] = -1;
return CountWays(n, x, n);
}
private int CountWays(int n, int x, int current) {
if (n == 0) return 1;
if (n < 0 || current <= 0) return 0;
if (dp[n, current] != -1) return dp[n, current];
long powValue = (long)Math.Pow(current, x);
int res = CountWays(n, x, current - 1);
if (powValue <= n) {
res = (res + CountWays(n - (int)powValue, x, current - 1)) % MOD;
}
dp[n, current] = res;
return res;
}
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NumOfWays(10, 2));
}
}This solution defines a recursive helper function which looks to utilize the current index raised to power `x` and whether it can fit into the sum to obtain the target `n`, leveraging a memoization table to store intermediate results.
Time Complexity: O(n^2) due to recursive checks and memo table lookups.
Space Complexity: O(n^2) for memoization storage.
Approach 2: Dynamic Programming Table Approach
This approach implements a dynamic programming table to compute the number of ways to represent n using a bottom-up method. By iterating through potential base numbers and powers systematically, it fills a table that records number of valid combinations.
def numOfWays(n, x):
MOD = 1000000007
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, int(n**(1/x)) + 1):
power = i ** x
for j in range(n, power - 1, -1):
dp[j] = (dp[j] + dp[j - power]) % MOD
return dp[n]
print(numOfWays(10, 2))public class NumOfWaysDP {
static final int MOD = 1000000007;
public int numOfWays(int n, int x) {
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; Math.pow(i, x) <= n; ++i) {
int power = (int) Math.pow(i, x);
for (int j = n; j >= power; --j) {
dp[j] = (dp[j] + dp[j - power]) % MOD;
}
}
return dp[n];
}
public static void main(String[] args) {
NumOfWaysDP obj = new NumOfWaysDP();
System.out.println(obj.numOfWays(10, 2));
}
}#include <iostream>
#include <vector>
#include <cmath>
#define MOD 1000000007
using namespace std;
int numOfWays(int n, int x) {
vector<int> dp(n + 1);
dp[0] = 1;
for (int i = 1; pow(i, x) <= n; ++i) {
int power = pow(i, x);
for (int sum = n; sum >= power; --sum) {
dp[sum] = (dp[sum] + dp[sum - power]) % MOD;
}
}
return dp[n];
}
int main() {
int n = 10, x = 2;
cout << numOfWays(n, x) << endl;
return 0;
}const numOfWays = function(n, x) {
const MOD = 1000000007;
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
for (let i = 1; Math.pow(i, x) <= n; ++i) {
const power = Math.pow(i, x);
for (let j = n; j >= power; --j) {
dp[j] = (dp[j] + dp[j - power]) % MOD;
}
}
return dp[n];
};
console.log(numOfWays(10, 2));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MOD 1000000007
int numOfWays(int n, int x) {
int* dp = (int*)calloc(n+1, sizeof(int));
dp[0] = 1;
for (int i = 1; pow(i, x) <= n; ++i) {
int power = pow(i, x);
for (int j = n; j >= power; --j) {
dp[j] = (dp[j] + dp[j - power]) % MOD;
}
}
int result = dp[n];
free(dp);
return result;
}
int main() {
printf("%d\n", numOfWays(10, 2));
return 0;
}using System;
class Program {
private const int MOD = 1000000007;
public static int NumOfWays(int n, int x) {
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; Math.Pow(i, x) <= n; ++i) {
int power = (int)Math.Pow(i, x);
for (int j = n; j >= power; --j) {
dp[j] = (dp[j] + dp[j - power]) % MOD;
}
}
return dp[n];
}
static void Main() {
Console.WriteLine(NumOfWays(10, 2));
}
}Iteratively calculate the power values and update the `dp` array indicating different sums possible as powers get subtracted from the target sum n.
Time Complexity: O(n^2)
Space Complexity: O(n) for the simple DP array used to store ways.
Approach 3: 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].
For each positive integer i, we can choose to either include it or not:
- Not include it: the number of ways is
f[i-1][j]; - Include it: the number of ways is
f[i-1][j-i^x](provided thatj geq i^x).
Therefore, the state transition equation is:
$
f[i][j] = f[i-1][j] + (j geq i^x ? f[i-1][j-i^x] : 0)
Note that the answer can be very large, so we need to take modulo 10^9 + 7.
The time complexity is O(n^2), and the space complexity is O(n^2), where n$ is the given integer in the
function numberOfWays(n: number, x: number): number {
const mod = 10 ** 9 + 7;
const f = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i <= n; ++i) {
const k = Math.pow(i, x);
for (let 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];
}func numberOfWays(n int, x int) int {
const mod int = 1e9 + 7
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, n+1)
}
f[0][0] = 1
for i := 1; i <= n; i++ {
k := int(math.Pow(float64(i), float64(x)))
for 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]
}impl Solution {
pub fn number_of_ways(n: i32, x: i32) -> i32 {
const MOD: i64 = 1_000_000_007;
let n = n as usize;
let x = x as u32;
let mut f = vec![vec![0; n + 1]; n + 1];
f[0][0] = 1;
for i in 1..=n {
let k = (i as i64).pow(x);
for j in 0..=n {
f[i][j] = f[i - 1][j];
if j >= k as usize {
f[i][j] = (f[i][j] + f[i - 1][j - k as usize]) % MOD;
}
}
}
f[n][n] as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(n^2) due to recursive checks and memo table lookups. Space Complexity: O(n^2) for memoization storage. |
| Dynamic Programming Table Approach | Time Complexity: O(n^2) Space Complexity: O(n) for the simple DP array used to store ways. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n * k) | O(n * k) | Best for interviews and quick implementation. Clearly models include/exclude decisions. |
| Dynamic Programming Table | O(n * k) | O(n * k) | Good when recursion depth is undesirable and when converting to classic subset-sum DP. |
Frequently asked questions
Is Ways to Express an Integer as Sum of Powers easy or hard?
Ways to Express an Integer as Sum of Powers is generally considered a medium difficulty dynamic programming problem. The main challenge is recognizing that distinct powers create a subset-sum counting problem and structuring the recursion or DP transitions correctly.
Ways to Express an Integer as Sum of Powers Python/Java solution
In Python or Java, the typical implementation uses recursion with memoization or a bottom-up DP table. Both approaches iterate over possible powers i^x and update counts for remaining sums until reaching the target n.
How to solve Ways to Express an Integer as Sum of Powers in O(n)?
A strict O(n) solution is not typical for this problem because each possible base power must be considered. The closest efficient solution is O(n * k) dynamic programming, where k = floor(n^(1/x)). The algorithm behaves like a 0/1 subset sum counting problem over values i^x.
What is the best approach for Ways to Express an Integer as Sum of Powers?
The most practical approach is recursive backtracking with memoization. Treat each value i^x as a candidate and decide whether to include or skip it while tracking the remaining sum. Caching states (index, remaining) avoids recomputation and reduces complexity to roughly O(n * k), where k = floor(n^(1/x)).
Is Ways to Express an Integer as Sum of Powers asked at Google/Amazon/Meta?
This problem pattern appears in interviews that test dynamic programming and subset-sum style reasoning. Variations of power-sum or subset counting problems have been reported in interviews at companies like Google, Amazon, and other large tech firms where DP fundamentals are expected.
What data structure is used in Ways to Express an Integer as Sum of Powers?
The solution primarily uses dynamic programming structures such as a 2D DP table or a memoization cache (hash map or array). The algorithm also stores precomputed power values i^x up to n and processes them similarly to a 0/1 knapsack problem.
What is the time complexity of Ways to Express an Integer as Sum of Powers?
The optimized dynamic programming and memoized recursion solutions run in O(n * k) time, where k is the number of valid bases such that i^x ≤ n. Space complexity is also O(n * k) due to memoization or the DP table storing counts for each intermediate sum.