2787. Ways to Express an Integer as Sum of Powers

[mah-shamim]

Topics: Dynamic Programming, Biweekly Contest 109

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

Hint:

1. You can use dynamic programming, where dp[k][j] represents the number of ways to express k as the sum of the x^th power of unique positive integers such that the biggest possible number we use is j.
2. To calculate dp[k][j], you can iterate over the numbers smaller than j and try to use each one as a power of x to make our sum k.

[mah-shamim]

We need to count the number of ways a given positive integer n can be expressed as the sum of unique positive integers each raised to the x-th power. The solution involves dynamic programming to efficiently compute the number of valid combinations without repetition.

Approach

1. Problem Analysis: The problem requires finding all sets of unique positive integers such that the sum of each integer raised to the x-th power equals n. The solution must avoid duplicate sets (e.g., {1, 2} and {2, 1} are considered the same set) and each integer can be used at most once.
2. Dynamic Programming Setup: We use a dynamic programming array dp where dp[j] represents the number of ways to achieve the sum j using the integers processed so far. Initialize dp[0] to 1 (the base case representing the empty set).
3. Determine Maximum Integer: Calculate the largest integer maxi such that maxix is less than or equal to n. This bounds the integers we need to consider.
4. DP Array Update: For each integer i from 1 to maxi, compute v = ix. Update the dp array in reverse order (from n down to v) to ensure each integer is used only once in each combination. For each j, update dp[j] by adding dp[j - v], which represents the number of ways to form j by including i.
5. Modulo Operation: Since the result can be large, all updates are performed modulo 10⁹ + 7.

Let's implement this solution in PHP: 2787. Ways to Express an Integer as Sum of Powers

<?php
/**
 * @param Integer $n
 * @param Integer $x
 * @return Integer
 */
function numberOfWays($n, $x) {
    $mod = 1000000007;
    $dp = array_fill(0, $n + 1, 0);
    $dp[0] = 1;

    $max_i = 1;
    while (pow($max_i, $x) <= $n) {
        $max_i++;
    }
    $max_i--;

    for ($i = 1; $i <= $max_i; $i++) {
        $v = (int)pow($i, $x);
        for ($j = $n; $j >= $v; $j--) {
            $dp[$j] = ($dp[$j] + $dp[$j - $v]) % $mod;
        }
    }

    return $dp[$n] % $mod;
}

// Test cases
echo numberOfWays(10, 2) . "\n"; // Output: 1
echo numberOfWays(4, 1) . "\n";  // Output: 2
?>

Explanation:

1. Initialization: The dp array is initialized with zeros, except for dp[0] which is set to 1. This array will store the number of ways to achieve each sum from 0 to n.
2. Finding maxi: The loop calculates the largest integer maxi such that maxix does not exceed n. This determines the range of integers we need to consider for the sum.
3. Dynamic Programming Update: For each integer i from 1 to maxi:
   • Compute v = ix.
   • Update the dp array from n down to v to ensure each integer is only used once per combination. For each j, the value dp[j] is incremented by dp[j - v], representing the inclusion of i in the sum.
4. Result Extraction: The result is found in dp[n], which gives the number of valid combinations modulo 10⁹ + 7.

This approach efficiently counts all unique combinations of integers raised to the x-th power that sum to n using dynamic programming, ensuring optimal performance even for the upper constraint limits.

[kovatz]

Thanks for solving the problem of "Ways to Express an Integer as Sum of Powers"

[mah-shamim]

Thanks