How to find the xth decibinary number?

Question

Hackerrank has a problem called Decibinary numbers which are essentially numbers with 0-9 digit values but are exponentiated using powers of 2. The question asks us to display the xth decibinary number. There is another twist to the problem. Multiple decibinary numbers can equal the same decimal number. For example, 4 in decimal can be 100, 20, 12, and 4 in decibinary.

At first, I thought that finding how many decibinary numbers for a given decimal number would be helpful. I consulted this post for a bit help ( https://math.stackexchange.com/questions/3540243/whats-the-number-of-decibinary-numbers-that-evaluate-to-given-decimal-number ). The post was a bit too hard to understand but then I also realized that even though we have how many decibinary numbers a decimal number can have, this doesn't help FINDING them (at least to my knowledge) which is the original goal of the question.

I do realize that for any decimal number, the largest decibinary number for it will simply be its binary representation. For ex, for 4 it is 100. So the brute force approach would be to check all numbers in this range for each decimal number and see if their decibinary representation evaluates to the given decimal number, but it is clearly evident that this approach will never pass since the input constraints define x to be from 1 to 10^16. Not only that, we have to find the xth decibinary number for a q amount of queries where q is from 1 to 10^5.

This question falls under the section of dp but I am confused how dp will be used or how it is even possible. In order for calculating the xth decibinary number q times (which is described in the brute force method above) it would be better to use a table (like the problem suggests). But for that, we would need to store and calculate 10^16 integers since that is the how big x can be. Assuming an integer is 4 Bytes, 4B * 10^16 ~= 4B * (2^3)^16 = 2^50 Bytes.

Can someone please explain how this problem is solved optimally. I am still new to CP so if I have made an error in something, please let me know.

(see link below for full problem statement): https://www.hackerrank.com/challenges/decibinary-numbers/problem

Answer 1

This is solvable with about 80 MB of data. I won't give code, but I will explain the strategy.

Build a lookup count[n][i] that gives you the number of ways to get the decimal number n using the first i digits. You start by inserting 0 everywhere, and then put a 1 in count[0][0]. Now start filling in using the rule:

count[n][i] = count[n][i-1] + count[n - 2**i][i-1] + count[n - 2*2**i][i-1] + ... + count[n - 9*2**i][i-1]

It turns out that you only need the first 19 digits, and you only need counts of n up to 2**19-1. And the counts all fit in 8 byte longs.

Once you have that, create a second data structure count_below[n] which is the count of how many decibinary numbers will give a value less than n. Use the same range of n as before.

And now a lookup proceeds as follows. First you do a binary search on count_below to find the last value that has less than your target number below it. Subtracting count_below from your query, you know which decibinary number of that value you want.

Next, search through count[n][i] to find the i such that you get your target query with i digits, and not with less. This will be the position of the leading digit of your answer. You then subtract off count[n][i-1] from your query (all the decibinaries with fewer digits). Then subtract off count[n-2**i][i-1], count[n-2* 2**i][i-1], ... count[n-8*2**i][i-1] until you find what that leading digit is. Now you subtract the contribution of that digit from the value, and repeat the logic for finding the correct decibinary for that smaller value with fewer digits.

Here is a worked example to clarify. First the data structures for the first 3 digits and up to 2**3 - 1:

count = [
  [1, 1, 1, 1], # sum 0
  [0, 1, 1, 1], # sum 1
  [0, 1, 2, 2], # sum 2
  [0, 1, 2, 2], # sum 3
  [0, 1, 3, 4], # sum 4
  [0, 1, 3, 4], # sum 5
  [0, 1, 4, 6], # sum 6
  [0, 1, 4, 6], # sum 7
]

count_below = [
    0, 1, 2, 4, 6, 10, 14, 20, 26, ...
]

Let's find the 20th.

1. count_below[6] is 14 and count_below[7] is 20 so our decimal sum is 6.
2. We want the 20 - count_below[6] = 6th decibinary with decimal sum 6.
3. count[6][2] is 4 while count[6][3] is 6 so we have a non-zero third digit.
4. We want the count[6][3] - count[6][2] = 2 with a non-zero third digit.
5. count[1][6 - 2**2] is 2, so 2 have 3rd digit 1.
6. The third digit is 1
7. We are now looking for the second decibinary whose decimal sum is 2.
8. count[2][1] is 1 and count[2][2] is 2 so it has a non-zero second digit.
9. We want the count[2][2] - count[2][1] = 1st with a non-zero second digit.
10. The second digit is 1
11. The rest is 0 because 2 - 2**1 = 0.

And thus you find that the answer is 110.

Now for such a small number, this was a lot of work. But even for your hardest lookup you'll only need about 20 steps of a binary search to find your decimal sum, another 20 steps to find the position of the first non-zero digit, and for each of of those digits, you'll have to do 1-9 different calculations to find what that digit is. Which means only hundreds of calculations to find the number.