You are viewing a single comment's thread. Return to all comments →
Can anyone help suggest a further optimization for the following solution? (I've implemented it in python; it passes 6/11 tests and times out the rest).
1) Figure out the number of decibinary numbers corresponding to each decimal number using the following dynamic programming algorithm suggested by xinwzh:
g[dec][dig - 1] + g[dec - offset][dig - 1] + g[dec - 2 x offset][dig - 1] + g[dec - 3 x offset][dig - 1] + ... + g[dig - 1]
offset = 2^(dig - 1)
g[dec][length of g[dec] - 1]
2) Add up the number of decibinary numbers corresponding to each decimal from 0, 1, 2, 3, etc. until the total is greater than the query.
0, 1, 2, 3, etc.
3) Find the queried decibinary by either a) finding the first decibinary and cycling up n times, or b) finding the last and cycling down g[dec][len(gs[dec]) -1] - n times.
g[dec][len(gs[dec]) -1] - n
Does anyone see where I might be able to optimize something further?? Is it possible to find the nth decibinary number equal to a given decimal number without cycling through the way I'm doing? (This is the bottleneck.)