# HackerRank The Power Sum problem solution

In this HackerRank The Power Sum problem solution we need to find the number of ways that a given integer, X, can be expressed as the sum of the Nth powers of unique, natural numbers.

## Problem solution in Python.

```import math
import sys

def powSum(temp, N):

result = 0

for nmbr in temp:
result += int(math.pow(nmbr, N))

return result

def findAllDecompositions(X, N, upperBound, powSet, counter, result):
# stopping condition
if not powSet:
result.append(counter)
return

newCounter = counter
newPowSet = []

for mmbr in powSet:
indic = mmbr[-1]

for nmbr in range(indic+1, upperBound+1):
temp = []
temp.extend(mmbr)
temp.append(nmbr)

tempSum = powSum(temp, N)

if tempSum == X:
# print(temp)
newCounter += 1
elif tempSum < X:
newPowSet.append(temp)

findAllDecompositions(X, N, upperBound, newPowSet, newCounter, result)

def numberOfAllDecompositions():

inp = []

for line in sys.stdin:
inp.append(int(line))

X = inp[0]
N = inp[1]

upperBound = math.floor(math.pow(X, 1/N))
powSet = []
result = []

# initialize the counter first
if X == int(math.pow(upperBound, N)):
counter = 1
else:
counter = 0

for i in range(1, upperBound + 1):
powSet.append([i])

findAllDecompositions(X, N, upperBound, powSet, counter, result)

print(result[0])

if __name__ == "__main__":

numberOfAllDecompositions()```

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int power = sc.nextInt();
System.out.println(countSumPower(num,power,1,0,0));
}

public static int countSumPower(int num, int power, int curr, int carry, int count){
int sum = carry + (int) Math.pow(curr,power);
if (sum == num)
return 1;
else if (sum > num)
return 0;

count += countSumPower(num, power, curr+1, sum, 0); // choose curr
count += countSumPower(num, power, curr+1, carry, 0); // dont choose curr

return count;
}
}```

## Problem solution in C++.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int powersum (int x, int sums[], int index, int size) {
if (x == 0) {
return 1;
}
else if (index == size) {
return 0;
}
int count = 0;

count += powersum(x, sums, index+1, size);
count += powersum(x - sums[index], sums , index+1, size);

return count;
}
int main() {
int num, root;
cin >> num >> root;
int sums[(int)pow(num, 1.00/root)];
int index = 0;
for (int i=1;i<=pow(num, 1.00/root);i++) {
sums[index] = (pow(i, root));
index++;
}
cout << powersum(num, sums, 0, (int)pow(num, 1.00/root));
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}```

## Problem solution in C.

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void recursive(int val, int p, int i, int max, int total, int *count)
{
int new_total = total + pow(i,p);

if(new_total > val)
return;
if(new_total == val)
{
*count += 1;
return;
}
if(i > max)
return;
int j;
for(j = i+1; j <= max; j++)
{
recursive(val, p, j, max, new_total, count);
}
return;
}

int nbr_of_poss(int val, int p)
{
int max = sqrt(val);
int count = 0;
recursive(val, p, 0, max, 0, &count);
return count;
}

int main()
{
int val, p;
scanf("%d%d", &val, &p);

printf("%d", nbr_of_poss(val, p));
return 0;
}```