Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each positive base supplies one optional value, its xth power, and bases cannot repeat. Counting subsets of these power values is a 0/1 knapsack problem, with sum zero initially attainable in one way: choosing nothing.

Approach

Initialize dp[0] = 1 and other sum counts to zero. Generate powers in increasing base order until a power exceeds n. For each power, scan target sums downward and add dp[sum - power] into dp[sum], modulo 10^9 + 7. Descending updates prevent using the same base more than once. Processing bases in fixed order counts each subset once rather than counting different addition orders. Return dp[n].

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (n + 1)
        dp[0] = 1

        for i in range(1, n + 1):
            power = i ** x
            if power > n:
                break
            for j in range(n, power - 1, -1):
                dp[j] = (dp[j] + dp[j - power]) % MOD

        return dp[n]

Complexity analysis

Let a = floor(n^(1/x)) be the number of usable positive bases. Time: O(a * n) for the reverse 0/1-knapsack updates. Auxiliary space: O(n) for the one-dimensional DP array.