#2787
Ways to Express an Integer as Sum of Powers
specialist · 870 · lc medium +31 · verified · 49.9% accepted · 844 likes · top 37%
Description
Two positive integers n and x are given.
Return the number of ways to express n as a sum of x-th powers of distinct positive integers — that is, the count of sets [n1, n2, ..., nk] of unique integers satisfying n = n1x + n2x + ... + nkx.
Since the result may be very large, return it modulo 109 + 7.
For example, if n = 160 and x = 3, one valid decomposition 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.
Code
1
2
3