Scale Engineer

Ways to Express an Integer as Sum of Powers

Med
#2499Time: 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).
Patterns
Dynamic Programming

Prompt

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 <= 300
  • 1 <= 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 target is 0, a valid combination is found. Return 1.
  • Base Case 2: If target is negative, or if num^x is greater than target, this path is invalid. Return 0.
  • Recursive Step: Explore two choices for the current number num:
    • Include num^x: Recursively call countWays(target - num^x, num + 1, x).
    • Exclude num^x: Recursively call countWays(target, num + 1, x).
  • 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:

  1. Include num^x: If we use num^x, the new target becomes target - num^x, and we move to the next integer num + 1 to ensure uniqueness.
  2. Exclude num^x: If we don't use num^x, the target remains the same, and we move to num + 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.

Solutions

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];  }}

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.

← Previous

Previous problem

Next →

Next problem