2882. Ways To Express An Integer As Sum Of Powers¶
Difficulty: Medium
LeetCode Problem View on GitHub
2882. Ways to Express an Integer as Sum of Powers
Medium
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
Solution¶
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
private int dp[][];
private int mod = 1000000007;
public int numberOfWays(int n, int x) {
ArrayList<Integer> arr = new ArrayList<>();
int idx = 1;
while (true) {
int current = (int)(Math.pow(idx++, x));
if (current > n)
break;
arr.add(current);
}
dp = new int[arr.size() + 1][n + 1];
for (int current[] : dp)
Arrays.fill(current, -1);
int res = solve(0, n, arr);
return res;
}
private int solve(int ind, int sumLeft, ArrayList<Integer> arr) {
if (sumLeft == 0)
return 1;
if (ind >= arr.size()) {
if (sumLeft == 0)
return 1;
return 0;
}
if (dp[ind][sumLeft] != -1)
return dp[ind][sumLeft];
int op1 = solve(ind + 1, sumLeft, arr);
int op2 = 0;
if (sumLeft >= arr.get(ind))
op2 = solve(ind + 1, sumLeft - arr.get(ind), arr);
return dp[ind][sumLeft] = (op1 + op2) % mod;
}
}
Complexity Analysis¶
- Time Complexity:
O(?) - Space Complexity:
O(?)
Approach¶
Detailed explanation of the approach will be added here