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.<p>Medium</p> <p>Given two <strong>positive</strong> integers <code>n</code> and <code>x</code>.</p> <p>Return <em>the number of ways</em> <code>n</code> <em>can be expressed as the sum of the</em> <code>x<sup>th</sup></code> <em>power of <strong>unique</strong> positive integers, in other words, the number of sets of unique integers</em> <code>[n<sub>1</sub>, n<sub>2</sub>, &hellip;, n<sub>k</sub>]</code> <em>where</em> <code>n = n<sub>1</sub><sup>x</sup> + n<sub>2</sub><sup>x</sup> + &hellip; + n<sub>k</sub><sup>x</sup></code><em>.</em></p> <p>Since the result can be very large, return it modulo <code>10<sup>9</sup> + 7</code>.</p> <p>For example, if <code>n = 160</code> and <code>x = 3</code>, one way to express <code>n</code> is <code>n = 2<sup>3</sup> + 3<sup>3</sup> + 5<sup>3</sup></code>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> n = 10, x = 2</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong></p> <p>We can express n as the following: n = 3<sup>2</sup> + 1<sup>2</sup> = 10.</p> <p>It can be shown that it is the only way to express 10 as the sum of the 2<sup>nd</sup> power of unique integers.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> n = 4, x = 1</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong></p> <p>We can express n in the following ways:</p> <ul> <li> <p>n = 4<sup>1</sup> = 4.</p> </li> <li> <p>n = 3<sup>1</sup> + 1<sup>1</sup> = 4.</p> </li> </ul> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= n <= 300</code></li> <li><code>1 <= x <= 5</code></li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • numberOfWays

      public int numberOfWays(int n, int x)