Find ways an Integer can be expressed as sum of n-th power of unique natural numbers in C++

In this tutorial, we are going to write a program that find the number of ways a integer can be expressed as sum of given n-th power of unique numbers.

We have two integers number and power. And we need to find in how many ways can we represent the given number as sum of n-th power of unique natural numbers. Let's see an example.

Input − number = 50, power = 2

Output − 3

There is only possible way we can write 4 as sum of 2 powers.

We will be using recursion to solve the problem. Let's see the steps to solve the problem.

• Initialize the number and power.

• Write a recursive function with a suitable name. It accepts number, power and i as arguments.

• If the number is less than zero or pow(i, power) is greater than number, then return 0.

• If the number is zero or pow(i, power) is equal to the number, then return 1.

• We have two recursive calls for the functions to compute the total number of ways

  • Increment the i.

  • In the first recursive call, check for the numbers less than given number.

  • In the second recursive call, check for the given number.

Example

Let's see the code.

 Live Demo

#include <bits/stdc++.h> using namespace std; int findPossibleWaysCount(int number, int power, int i = 1) {    if(number < 0 || number < pow(i, power)) {       return 0;    }    if(number == 0 || number == pow(i, power)) {       return 1;    }    return findPossibleWaysCount(number - pow(i, power), power, i + 1) + findPossibleWaysCount(number, power, i + 1); } int main() {    // initializing the number and power    int number = 50, power = 2;    cout << findPossibleWaysCount(number, power) << endl;    return 0; }

Output

If you run the above code, then you will get the following result.

3

Conclusion

If you have any queries in the tutorial, mention them in the comment section.