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.
c++ solution.
Using one pass recursion and boundary strategy.
In each recursion, searched range is bounded by upper and lower bound.
intpowerSum(intx,intn){classPower_sum_helper{private:intnum_of_comb{0};intn;voidinner_power_sum(inttarget,intprev_candidate){// - searched range: a < i <= b// a: the max num satisfing a^(N+1) <= target// b: min(prev_candidate-1, c)// c: the max num satisfing c <= target**(1/N)intupper{min(prev_candidate-1,static_cast<int>(pow(target,1.0/n)))};for(inti=upper;pow(i,n+1)>=target;--i){intpowed_i{static_cast<int>(pow(i,n))};if(powed_i==target)++num_of_comb;elseinner_power_sum(target-powed_i,i);}}public:Power_sum_helper(int_n):n{_n}{}intget_num_of_comb()const{returnnum_of_comb;}voidinner_power_sum(inttarget){inner_power_sum(target,numeric_limits<int>::max());}};if(x<1)return0;Power_sum_helperhelper{n};helper.inner_power_sum(x);returnhelper.get_num_of_comb();}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Power Sum
You are viewing a single comment's thread. Return to all comments →
c++ solution.
Using one pass recursion and boundary strategy.
In each recursion, searched range is bounded by upper and lower bound.