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.

HackerRank The Power Sum problem solution


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