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:

• where g[dec][dig] gives the number of decibinary numbers equal in value to decimal {dec} with at most {dig} digits, you can get g[dec][dig] from: g[dec][dig - 1] + g[dec - offset][dig - 1] + g[dec - 2 x offset][dig - 1] + g[dec - 3 x offset][dig - 1] + ... + g[0][dig - 1], where offset = 2^(dig - 1).
• Total number of decibinary numbers equal to a given decimal number is retrieved by: 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.

• The decimal that put it over the list is the decimal corresponding to the queried decibinary.
• The queried decibinary will be the nth decibinary of that decimal, where n is the difference between the query and the previous total (i.e. all the decibinaries up to but not including the decimal corresponding to the queried decibinary).

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.

• Find the next highest decibinary corresponding to the same decimal number by incrementing up the digits and looking for the first pair of digits where you can subtract two from the lower digit and add one to the higher digit. i.e., 200 -> 1000, 54 -> 62. However, you also need to go back down the digits and maximize in the other direction: 1900 -/-> 2700, 1900 -> 2188.
• Find the next lowest decibinary by the same thing, but reversed

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.)