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 can't believe I spend 5 hours on a single question. Worth it though!
Anyway, here's the solution in C++
#define u uint64_tvector<vector<u>>dp(285113,vector<u>(20,-1));vector<u>prefixSum(285113,0);urecur(unum,ubits){if(dp[num][bits]!=-1)returndp[num][bits];if(bits==1)returndp[num][bits]=((num<10)?1:0);uval=0,ans=0,powerOfTwo=pow(2,bits-1);for(inti=0;i<10;++i){if(num<val)break;ans+=recur(num-val,bits-1);val+=powerOfTwo;}returndp[num][bits]=ans;}constintiife=[]{dp[0][1]=1;dp[1][1]=1;prefixSum[0]=1;prefixSum[1]=2;unextPowerOfTwo=2,bits=1;ui=2;for(;i<285113;++i){if(i==nextPowerOfTwo){nextPowerOfTwo*=2;++bits;}prefixSum[i]=prefixSum[i-1]+recur(i,bits);}return1;}();voidfunc(long&count,longnum,longbits,longnth,vector<long>&res){if(dp[num][bits]>=0&&count+dp[num][bits]<nth){count+=dp[num][bits];return;}if(bits==1){if(num<10){++count;res[bits-1]=num;}return;}longpowerOfTwo=pow(2,bits-1),val=0,i=0;while(count!=nth&&val<=num){res[bits-1]=i;func(count,num-val,bits-1,nth,res);val+=powerOfTwo;++i;}return;}longdecibinaryNumbers(longx){if(x==1)return0;if(x==2)return1;autoitr=lower_bound(prefixSum.begin(),prefixSum.end(),(u)(x));longdecimalValue=itr-prefixSum.begin();longnth=x-prefixSum[decimalValue-1];longbits=log2(decimalValue)+1;vector<long>res(bits,0);longcount=0;func(count,decimalValue,bits,nth,res);longans=0;for(inti=res.size()-1;i>=0;--i){ans=ans*10+res[i];}returnans;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Decibinary Numbers
You are viewing a single comment's thread. Return to all comments →
I can't believe I spend 5 hours on a single question. Worth it though! Anyway, here's the solution in C++