Package g2701_2800.s2787_ways_to_express_an_integer_as_sum_of_powers

Class Solution

java.lang.Object

g2701_2800.s2787_ways_to_express_an_integer_as_sum_of_powers.Solution

public class Solution
extends Object

2787 - Ways to Express an Integer as Sum of Powers.

Medium

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 = 3² + 1² = 10.

It can be shown that it is the only way to express 10 as the sum of the 2^nd power of unique integers.

Example 2:

Input: n = 4, x = 1

Output: 2

Explanation:

We can express n in the following ways:

• n = 4¹ = 4.

• n = 3¹ + 1¹ = 4.

Constraints:

• 1 <= n <= 300
• 1 <= x <= 5

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	numberOfWays(int n, int x)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Solution

public Solution()

Method Detail

numberOfWays

public int numberOfWays(int n,
                        int x)