## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# The power sum challenge

Sharing is caring!

Find the number of ways that a given integer, $X$, can be expressed as the sum of the $N^{th}$ power of unique, natural numbers.

Input Format
The first line contains an integer $X$.
The second line contains an integer $N$.

Constraints
$1 \le X \le 1000$
$2 \le N \le 10$

Output Format
Output a single integer, the answer to the problem explained above.

Sample Input 0

```10
2
```

Sample Output 0

```1
```

Explanation 0
If $X = 10$ and $N=2$, we need to find the number of ways that $10$ can be represented as the sum of squares of unique numbers.

$10 = 1^2 + 3^2$

This is the only way in which $10$ can be expressed as the sum of unique squares.

Sample Input 1

```100
2
```

Sample Output 1

```3
```

Explanation 1
$100 = 10^2 = 6^2 + 8^2 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2$

Sample Input 2

```400
2
```

Sample Output 2

```55
```

Solution

```public class ThePowerSum {
private static int solve(int x, int n, int num, double sum) {
if (sum == x) {
return 1;
} else {
int ans = 0;
if (sum < x) {
for (int i = num; i <= Math.pow(x, 1.0 / n); i++) {
ans += solve(x, n, i + 1, sum + Math.pow(i, n));
}
}
return ans;
}
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
Scanner in = new Scanner(System.in);

int x = in.nextInt();
int n = in.nextInt();

System.out.println(solve(x, n, 1, 0));
}
}
```