The Power Sum
MediumP3Coding
Count the ways to write x as a sum of n-th powers of distinct positive integers. Order does not matter, and each base can be used at most once.
For example, with x = 100 and n = 2, 100 = 10^2, 100 = 6^2 + 8^2 and 100 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2, so the answer is 3.
Example 1
- Input
- x = 10, n = 2
- Output
- 1
- Why
- 10 = 1^2 + 3^2 is the only way.
Example 2
- Input
- x = 100, n = 2
- Output
- 3
Example 3
- Input
- x = 100, n = 3
- Output
- 1
Constraints
- 1 <= x <= 500
- 1 <= n <= 10
- The answer fits in a 53-bit integer.
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 12. ⌘Enter runs, ⌘⇧Enter submits.