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));
    }
}