The Power Sum


Problem Statement :


Find the number of ways that a given integer, X , can be expressed as the sum of the  Nth powers of unique, natural numbers.

For example, if X =  13 and N =  2 , we have to find all combinations of unique squares adding up to 13. The only solution is 2^2 + 3^2.

Function Description

Complete the powerSum function in the editor below. It should return an integer that represents the number of possible combinations.

powerSum has the following parameter(s):

X: the integer to sum to
N: the integer power to raise numbers to


Input Format

The first line contains an integer X.
The second line contains an integer N.

Constraints

1  <=   X  <=  1000
2  <=   N   <=   10

Output Format

Output a single integer, the number of possible combinations caclulated.


Solution :



title-img 


                            Solution in C :

In   C++  :





#include <iostream>
#include <vector>

using namespace std;

int power (int a, int n) {
    if(n == 0)
        return 1;
    // else
    if(n % 2 == 0) {
        int temp = power(a, n / 2);
        return temp * temp;
    }
    // else
    return a * power(a, n - 1);
}

int solve(int x, const vector<int> &powers, int index) {
    if(index == 0) {
        return (x == 1) ? 1 : 0;
    }
    // else
    if(x == powers[index])
        return 1 + solve(x, powers, index - 1);
    // else
    int res = 0;
    res += solve(x - powers[index], powers, index - 1);
    res += solve(x, powers, index - 1);
    return res;
}


int main() {
    int x, n;
    cin >> x >> n;
    
    int pow = 1;
    vector<int> powers;
    for(int a = 2; pow <= x; a++) {
        powers.push_back(pow);
        pow = power(a, n);
    }
    
    cout << solve(x, powers, powers.size() - 1) << endl;        
    return 0;
}







In     Java  :




import java.util.Scanner;


public class PowerSum {
	int count=0;
	int sum;
	int pow;
    public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int x=in.nextInt();
		int n=in.nextInt();
        PowerSum p=new PowerSum();
        p.sum=x;
        p.pow=n;
        int N=(int)Math.pow(x, (1.0/n));
        p.getcount(p.sum,N,true);
        p.getcount(p.sum,N,false);
        System.out.println(p.count);
        in.close();
	}
    void getcount(int sum1,int n,boolean lenyani){
    	
    	if(lenyani==true){
    		sum1=sum1-(int)Math.pow(n, pow);
    	
    	}
    	if(sum1<0) return;
    	if(sum1==0){
    		count++;
    		return;
    	}
    	if(n==1) return;
    	getcount(sum1,n-1,true);
    	getcount(sum1,n-1,false);
    }
 
}








In    C   :







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

int the_power_sum(int n, int m,int p){
    int tmp = pow(m,p);
    if(tmp == n) return 1;
    if(tmp > n) return 0;
 return the_power_sum(n,m+1,p) + the_power_sum(n-tmp, m+1,p);
}
int main() {
    int n,p;
    scanf("%d%d",&n,&p);
    printf("%d", the_power_sum(n,1,p));
 
    return 0;
}









In   Python3 :





import sys
X = int(input())
N = int(input())

def rec(X,N,start):
    count = 0 
    for i in range(start,X):
        ans = X-i**N
        if ans == 0:
            count += 1
        if ans> 0 :
            count += rec(ans,N,i+1)
        if ans<0:
            continue   
    return count
    
print(rec(X,N,1))








View More Similar Problems

Array-DS

An array is a type of data structure that stores elements of the same type in a contiguous block of memory. In an array, A, of size N, each memory location has some unique index, i (where 0<=i<N), that can be referenced as A[i] or Ai. Reverse an array of integers. Note: If you've already solved our C++ domain's Arrays Introduction challenge, you may want to skip this. Example: A=[1,2,3

View Solution →

2D Array-DS

Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t

View Solution →

Dynamic Array

Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.

View Solution →

Left Rotation

A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d

View Solution →

Sparse Arrays

There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun

View Solution →

Array Manipulation

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu

View Solution →