Given two numbers num and power as input. The goal is to find the ways in which num can be represented as a sum of unique natural numbers raised to the given power. If num is 10 and power is 2 then we can represent 10 as 12+32. So total 1 way.
For Example
Input
num=30
Output
Count of ways to express a number as sum of powers are: 2
Explanation
The ways in which we can express 30 as sum of powers: 12 + 22 + 52 and 12 + 22 + 32 + 42
Input
num=35
Output
Count of ways to express a number as sum of powers are: 1
Explanation
The ways in which we can express ‘num’ as sum of powers: 22 + 32
Approach used in the below program is as follows −
In this approach we first check if the number is itself the power of any numpower. If yes then return ways as 1, if not then recursively check for sum numpower + (num+1)power.
Take two integers num and power as input.
Function sum_of_powers(int num, int power, int val) takes a num and returns the count of ways to express ‘num’ as sum of unique natural numbers raised to the given power.
Take check=(num − pow(val, power)). If check is 0 then return 1 as the number itself is valpower.
If check is less than 0 then return 0.
Otherwise take temp=val+1.
Return sum of ( sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp) ).
At the end we will get ways to return value.
Example
#include <bits/stdc++.h>
using namespace std;
int sum_of_powers(int num, int power, int val){
int check = (num − pow(val, power));
if(check == 0){
return 1;
}
else if(check < 0){
return 0;
} else {
int temp = val + 1;
return sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp);
}
}
int main(){
int num = 25, power = 2;
cout<<"Count of ways to express a number as sum of powers are: "<<sum_of_powers(num, power, 1);
return 0;
}Output
If we run the above code it will generate the following output −
Count of ways to express a number as sum of powers are: 2