2787. Ways to Express an Integer as Sum of Powers LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2787. Ways to Express an Integer as Sum of Powers LeetCode Solution with the best time and space complexity. The solution to Ways to Express an Integer as Sum of Powers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Ways to Express an Integer as Sum of Powers solution in C++
Ways to Express an Integer as Sum of Powers solution in Java
Ways to Express an Integer as Sum of Powers solution in Python
Additional Resources

2787. Ways to Express an Integer as Sum of Powers LeetCode Solution image

Problem Statement of Ways to Express an Integer as Sum of Powers

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

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

2787. Ways to Express an Integer as Sum of Powers LeetCode Solution in C++

class Solution {
 public:
  int numberOfWays(int n, int x) {
    constexpr int kMod = 1'000'000'007;
    // dp[i] := the number of ways to express i
    vector<int> dp(n + 1);
    int ax;  // a^x

    dp[0] = 1;

    for (int a = 1; (ax = pow(a, x)) <= n; ++a)
      for (int i = n; i >= ax; --i) {
        dp[i] += dp[i - ax];
        dp[i] %= kMod;
      }

    return dp[n];
  }
};
/* code provided by PROGIEZ */

2787. Ways to Express an Integer as Sum of Powers LeetCode Solution in Java

class Solution {
  public int numberOfWays(int n, int x) {
    final int kMod = 1_000_000_007;
    // dp[i] := the number of ways to express i
    int[] dp = new int[n + 1];
    int ax; // a^x

    dp[0] = 1;

    for (int a = 1; (ax = (int) Math.pow(a, x)) <= n; ++a)
      for (int i = n; i >= ax; --i) {
        dp[i] += dp[i - ax];
        dp[i] %= kMod;
      }

    return dp[n];
  }
}
// code provided by PROGIEZ

2787. Ways to Express an Integer as Sum of Powers LeetCode Solution in Python

class Solution:
  def numberOfWays(self, n: int, x: int) -> int:
    kMod = 1_000_000_007
    # dp[i] := the number of ways to express i
    dp = [1] + [0] * n

    for a in range(1, n + 1):
      ax = a**x
      if ax > n:
        break
      for i in range(n, ax - 1, -1):
        dp[i] += dp[i - ax]
        dp[i] %= kMod

    return dp[n]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents