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

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

by

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: