# Java Program to Find Number of Ways to Express a Number as Sum of Powers Using Recursion

In the previous article, we have discussed about Java Program to Find Sum of Proper Divisors of a Number by Using Recursion

In this article we are going to see how we can find the number of ways so that a number can be expressed as sum of powers by using recursion.

## Java Program to Find Number of Ways to Express a Number as Sum of Powers Using Recursion

As per the problem statement you have to find the number of ways so that a number can be expressed as sum of powers.

For example:

Number = 100 and Power = 2
Then 100 can be expressed as sum of powers as follows
10^2 OR
6^2+8^2 OR
1^2 + 3^2 + 4^2 + 5^2 + 7^2
So there are total 3 ways.

Let’s see the program to understand it more clearly.

### Method-1: Java Program to Find Number of Ways to Express a Number as Sum of Powers By Using Recursion & Static Input Value

Approach:

• Declare and initialize two integer variables say ‘num‘ and ‘power‘  respectively.
• Pass both of them to the user defined method countWays( )  that calls countWaysUtil( ) function which is a recursive function. It calculates the ways we can represent the number as a sum of numbers raised to the specific power.
• Print the result.

Program:

import java.util.*;
// Main class
public class Main
{
// Recursive method that finds ways to represent number as a sum of power
static int countWaysUtil(int x, int power, int num)
{
// Base cases
int val = (int) (x - Math.pow(num, power));
if (val == 0)
return 1;
if (val < 0)
return 0;
// Breaks into two cases one with num included and the other one without num
return countWaysUtil(val, power, num + 1) +
countWaysUtil(x, power, num + 1);
}

// Returns number of ways to express
// x as sum of numbers raised to the specified power
static int countWays(int x, int power)
{
return countWaysUtil(x, power, 1);
}

public static void main(String[] args)
{
int num = 100, power =2;
// call the method and store the ways
int ways = countWays(num,power);
System.out.println(num+" can be represented with power "+power+" in "+ways+" ways.");
}
}

Output:

100 can be represented with power 2 in 3 ways.

### Method-2: Java Program to Find Number of Ways to Express a Number as Sum of Powers By Using Recursion & User Input Value

Approach:

• Ask the user to enter a ‘num’ and ‘power’.
• Pass both of them to the countWays( ) function that calls countWaysUtil( ) function which is a recursive function. It calculates the ways we can represent the number as a sumof numbers raised to the specific power.
• Print the result.

Program:

import java.util.*;
// Main class
public class Main
{
// recursive method that finds ways to represent number as a sum of power
static int countWaysUtil(int x, int power, int num)
{
// Base cases
int val = (int) (x - Math.pow(num, power));
if (val == 0)
return 1;
if (val < 0)
return 0;
// Breaks into two cases
// one with num included and the other one without num
return countWaysUtil(val, power, num + 1) +
countWaysUtil(x, power, num + 1);
}

// Returns number of ways to express
// x as sum of numbers raised to the specified power
static int countWays(int x, int power)
{
return countWaysUtil(x, power, 1);
}

public static void main(String[] args)
{
// Asking the user for input
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number and power");
int num = sc.nextInt(), power =sc.nextInt();
// call the method and store the ways
int ways = countWays(num,power);
System.out.println(num+" can be represented with power "+power+" in "+ways+" ways.");
}
}

Output:

Enter the number and power
100 3
100 can be represented with power 3 in 1 ways.

Access the Simple Java program for Interview examples with output from our page and impress your interviewer panel with your coding skills.

Related Java Programs: