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 which is logically the same as the one posted previously but hopefully a little easier to understand.
constintdmax=300000;constintdigits=10;constintpowers=20;vector<vector<long>>v(dmax,vector<long>(powers));vector<long>c(dmax);// Complete the decibinaryNumbers function below.voidpreCompute(){// Compute the number of duplicates for each value, number of digits.for(inti=0;i<dmax;i++){v[i][0]=i<digits;for(intj=1;j<powers;j++){// Duplicates is sum of all shorter numbers duplicates for each digit.for(intk=0;k<digits;k++){intvalue=i-k*(1<<j);// Exit if using digit creates number larger than target value.if(value<0)break;v[i][j]+=v[value][j-1];}}}// Calculate the absolute offset for the first duplicate of each number.for(inti=1;i<dmax;i++){c[i]=v[i-1][powers-1]+c[i-1];}}longdecibinaryNumbers(longx){longresult=0;autol=upper_bound(c.begin(),c.end(),x-1)-1;intvalue=l-c.begin();longoffset=(x-1)-*l;// Find each digit.for(inti=powers-1;i>=1;i--){intpower=1<<i;// Find the digit which takes us closest to offset.for(intdigit=0;digit<digits;digit++){// Calculate value of remaining digits.intv1=value-digit*power;// If index is less than duplicates for remainder we have our digit.if(offset<v[v1][i-1]){result+=digit;value-=power*digit;break;}// Subtract number of duplicates for this digit from offset.offset-=v[v1][i-1];}result*=10;}// Whatever is left must be the last digit.result+=value;// cout << x << ":" << result << ":" << l - c.begin() << endl;returnresult;}
Decibinary Numbers
You are viewing a single comment's thread. Return to all comments →
C++ solution which is logically the same as the one posted previously but hopefully a little easier to understand.