Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2882. Ways to Express an Integer as Sum of Powers

My accepted Python solution to LeetCode problem 2882, Ways to Express an Integer as Sum of Powers, running in 282ms.

  • Difficulty: Medium
  • Python
  • Runtime 282ms
  • Memory 17.2MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 282ms, memory 17.2MB, accepted 2025-12-29.

python
class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        MOD = 10**9 + 7
        
        # Generate all x-th powers up to n
        powers = []
        i = 1
        while i ** x <= n:
            powers.append(i ** x)
            i += 1
        
        # DP: count ways to form sum using subset of powers
        # dp[j] = number of ways to form sum j
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for p in powers:
            # Process in reverse to avoid using same power twice
            for j in range(n, p - 1, -1):
                dp[j] = (dp[j] + dp[j - p]) % MOD
        
        return dp[n]

Source