LeetCode in Kotlin

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

Solution

class Solution {
    fun numberOfWays(n: Int, x: Int): Int {
        val dp = IntArray(301)
        val mod = 1000000007
        var v: Int
        dp[0] = 1
        var a = 1
        while ((Math.pow(a.toDouble(), x.toDouble())).also { v = it.toInt() } <= n) {
            for (i in n downTo v) {
                dp[i] = (dp[i] + dp[i - v]) % mod
            }
            a++
        }
        return dp[n]
    }
}

This site is open source. Improve this page.