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 <= 3001 <= x <= 5This approach utilizes recursion to explore all possible combinations of unique integers whose x-th powers sum up to n. To improve its efficiency, we apply memoization to cache the results of state computations and avoid redundant calculations.
We define a recursive function that reduces the target number by the current number raised to the power and recursively calls itself to find valid sequences, caching results along the way for efficiency.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the target number. This is due to the number of recursive calls and memoization lookup.
Space Complexity: O(n^2), for the storage used in memoization.
This approach implements a dynamic programming table to compute the number of ways to represent n using a bottom-up method. By iterating through potential base numbers and powers systematically, it fills a table that records number of valid combinations.
This solution initializes a table `dp` with `dp[0]` set to 1, indicating one way to sum up to zero. Using nested loops, it populates the ways to achieve each sum `j` using integers up to n raised to the power of x.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), iterating through combinations and using nested loops up to n.
Space Complexity: O(n), with an array proportional to n being used.
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(n^2), where n is the target number. This is due to the number of recursive calls and memoization lookup. Space Complexity: O(n^2), for the storage used in memoization. |
| Dynamic Programming Table Approach | Time Complexity: O(n^2), iterating through combinations and using nested loops up to n. Space Complexity: O(n), with an array proportional to n being used. |
Maximum Subarray - Kadane's Algorithm -- Leetcode 53 • Greg Hogg • 367,070 views views
Watch 9 more video solutions →Practice Ways to Express an Integer as Sum of Powers with our built-in code editor and test cases.
Practice on FleetCode