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;
}