Sum of powers

can anyone please tell what will be the properties of a variable c in equation a^x+b^y=c ???

1 Like

What exactly are you asking about? It’s just a sum of powers; the way you state the question, I can tell you that c can be anything, for example if x=y=1.

Do a,b,x,y satisfy some conditions? Are they integers, reals, can they be positive or negative? etc.

are you referring to this problem on hackerearth?

Can be solved by hashing all the perfect power pair sums with magnitude less than 1e6+1 and then checking if the test number is contained in that preprocessed map.

2 Likes

I Suppose that you are referring to the problem in Angel prime Hiring challenge in HackerEarth.

A number is to checked whether it is sum of perfect powers or not.

Perfect powers Series : 1,4,8,9,16…

so first create a hash table to store mark all the perfect powers and then for each given number check whether you can find two perfect powers that sum upto given number

this can be done in linear time ( after pre calculating the hash table )

Code for Clarification

 #include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    int t;
    int n;
    int a[1000000] = {0};
    a[1] = 1;
    for(int i = 2; i <= 1000;i++){
    	for(int j = 2;pow(i,j) <= 1000000;j++){
    		int pos = pow(i,j);
    		a[pos] = 1;
    	}
    }
    cin>>t;
    while(t--){
    	cin>>n;
    	bool chk = false;
    	for(int i = 1;i <= n/2 ; i++){
    		if(a[i] && a[n-i]) {
    			chk = true;
    			break;
    		}
    	}
    	if (chk) cout<<"Yes"<<endl;
    	else cout<<"No"<<endl;
    	}
return 0;    	
}
2 Likes