We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I noticed X was capped to 1000 and I'd never need to try any number >sqrt(1000), which happens to be just under 32.
So, what I did was precompute the Nth powers for [1..32], store my current set as a bitmap in a u32. and then add when the bit was on. I just iterated until the first power of 2 (which means it's a single element set) for which the sum (the actual Nth power, in this case) was > X, since that means it's the Nth root of X and thus no point trying anything else.
I'm somewhat proud of how dumb my solution was. No recursion, no algorithms concepts (although that's what I'm here to train :'( ).
fnpowers(N:i32)->[i32;32]{letmutP=[0i32;32];P[0]=1;for(i,j)in(1..32usize).zip(2..33i32){P[i]=j.pow(Nasu32);}P}fnpowerSumS(S:u32,P:&[i32])->i32{letmutacc=0;forbitin0..32{acc+=P[bit]*(S&(1<<bit)!=0)asi32;}acc}fnpowerSum(X:i32,N:i32)->i32{letmutcurrent_set=2u32;letmutcount=0;letP=powers(N);loop{letsum=powerSumS(current_set,&P);count+=(sum==X)asi32;// We never need to explore further from sqrt(X)ifcurrent_set.is_power_of_two()&&sum>X{break;}current_set+=1;}count}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
The Power Sum
You are viewing a single comment's thread. Return to all comments →
I noticed X was capped to 1000 and I'd never need to try any number >sqrt(1000), which happens to be just under 32. So, what I did was precompute the Nth powers for [1..32], store my current set as a bitmap in a
u32
. and then add when the bit was on. I just iterated until the first power of 2 (which means it's a single element set) for which the sum (the actual Nth power, in this case) was > X, since that means it's the Nth root of X and thus no point trying anything else. I'm somewhat proud of how dumb my solution was. No recursion, no algorithms concepts (although that's what I'm here to train :'( ).