2787. Ways to Express an Integer as Sum of Powers

Description

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 = 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.

 

Constraints:

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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(nlogn)
• Space complexity: O(nlogn)

 

JavaScript

/**
 * @param {number} n
 * @param {number} x
 * @return {number}
 */
const numberOfWays = function (n, x) {
  const MODULO = BigInt(10 ** 9 + 7);
  const powers = [];

  for (let base = 1; Math.pow(base, x) <= n; base++) {
    const power = Math.pow(base, x);

    powers.push(power);
  }

  const dp = Array.from({ length: n + 1 }, () => {
    return new Array(powers.length + 1).fill(-1);
  });

  const sumPower = (index, remainder) => {
    if (remainder === 0) return 1n;
    if (remainder < 0 || index >= powers.length) return 0n;
    if (dp[remainder][index] !== -1) return dp[remainder][index];
    let result = sumPower(index + 1, remainder);

    if (powers[index] <= remainder) {
      const nextRemainder = remainder - powers[index];

      result = (result + sumPower(index + 1, nextRemainder)) % MODULO;
    }

    dp[remainder][index] = result;

    return result;
  };

  return Number(sumPower(0, n));
};