[Solved] Entrance Test with Java, C++

“Success Academy” has arranged for a entrance test for High School students from rural villages. Those successful students of the test will be awarded the scholarship for their IIT/JEE preparations at Success Academy. Sunil, the co-coordinator and founder of the academy has given one problem for the first stage of the test. The problem goes like this:

Given two integers x and n, find the number of ways to express x as sum of n-th powers of unique natural numbers. It is given that 1 <= n <= 20.

Sunil himself has not computed the solution of the problem. Write a recursive method to help him find the answer for the same to evaluate the students.

Hence create a class named NumberofWays with the following method.

Create a driver class called Main. In the Main method, obtain input from the user in the console and display the number of ways to express x as sum of n-th powers of unique natural numbers by calling the countWays method present in the NumberofWays class.

[Note: Strictly adhere to the Object Oriented Specifications given in the problem statement.

All class names, attribute names and method names should be the same as specified in the problem statement.]
Input Format:
The first line of input contains the integer x.
The second line contains the integer n.

Output Format:
Output the number of ways to express x as sum of n-th powers of unique natural numbers in a single line.
Refer sample input and output for formatting specifications.

Sample Input 1:
100
2

Sample Output 1:
3

Sample Input 2:
100
3

Sample Output 2:
1

Solution

import java.util.*;
import static java.lang.Math.*;
public class Main {
    //sauravhathi
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        int n = in.nextInt();
        System.out.println(countWays(x, n));
    }
    public static int countWays(int x, int n) {
        return countWays(x, n, 1, 0);
        //sauravhathi
    }
    public static int countWays(int x, int n, int curr_num, int curr_sum) {
        int results = 0;
        int p = (int) Math.pow(curr_num, n);
        while (p + curr_sum < x) {
            results += countWays(x, n, curr_num + 1, p + curr_sum);
            curr_num++;
            //sauravhathi
            p = (int) Math.pow(curr_num, n);
        }
        if (p + curr_sum == x)
            results++;
        return results;
    }
}

#include <bits/stdc++.h>
using namespace std;

int power(int num, unsigned int n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        return power(num, n / 2) * power(num, n / 2);
    else
        return num * power(num, n / 2) * power(num, n / 2);
}

int countWays(int x, int n, int curr_num = 1,
                   int curr_sum = 0)
{
    int results = 0;
    int p = power(curr_num, n);
    while (p + curr_sum < x)
    {
        results += countWays(x, n, curr_num + 1,
                                  p + curr_sum);
        curr_num++;
        p = power(curr_num, n);
    }

    if (p + curr_sum == x)
        results++;
    return results;
}

int main()
{
    int x,n;
    cin >> x;
    cin >> n;
    cout << countWays(x, n);
    return 0;
}

Happy Learning – If you require any further information, feel free to contact me.