Decibinary for xth number (Python code)

Question

I created the code for the problem description below. It works for \$N\le10^6\$ but after that it gives a time out error. What I don't understand is how to optimize the code using dynamic programming. I have used a dictionary to create decibinary numbers with the formula mentioned in this OEIS post. for more description link: Hackerrank decibinary problem forum

Problem description:

Let's combine decimal and binary numbers in a new system we call decibinary! In this number system, each digit ranges from 0 to 9 (like the decimal number system), but the place value of each digit corresponds to the one in the binary number system. For example, the decibinary number 2016 represents the decimal number 24 because:

\$ (2016)_{decibinary}= 2\cdot2^3+0\cdot2^2+1\cdot2^1+6\cdot2^0 = (24)_{10} \$

Pretty cool system, right? Unfortunately, there's a problem: two different decibinary numbers can evaluate to the same decimal value! For example, the decibinary number 2008 also evaluates to the decimal value 24:

\$ (2008)_{decibinary}= 2\cdot2^3+0\cdot2^2+0\cdot2^1+8\cdot2^0 = (24)_{10}\$

This is a major problem because our new number system has no real applications beyond this challenge!

Consider an infinite list of non-negative decibinary numbers that is sorted according to the following rules:

• The decibinary numbers are sorted in increasing order of the decimal value that they evaluate to.
• Any two decibinary numbers that evaluate to the same decimal value are ordered by increasing decimal value, meaning the equivalent decibinary values are strictly interpreted and compared as decimal values and the smaller decimal value is ordered first.

You will be given q queries in the form of an integer, q. For each x, find and print the \$x^{\textrm{th}}\$ decibinary number in the list on a new line.

Function Description

Complete the decibinaryNumbers function in the editor below. For each query, it should return the decibinary number at that one-based index.

decibinaryNumbers has the following parameter(s):

x: the index of the decibinary number to return

Input Format

The first line contains an integer, \$q\$, the number of queries. Each of the next \$q\$ lines contains an integer, \$x\$, describing a query.

Constraints:

\$ 1 \le q \le 10^5 \$

\$ 1 \le x \le 10^{16} \$

Output Format

For each query, print a single integer denoting the the xth decibinary number in the list. Note that this must be the actual decibinary number and not its decimal value. Use 1-based indexing.

Sample Input 0

5
1
2
3
4
10

Sample Output 0

0
1
2
10
100

Additional samples omitted…

#!/bin/python3

import math
import os
import random
import re
import sys
from math import floor
from collections import defaultdict

a={0:0,1:1,2:2,3:3}

for i in range(4,10**6):
    a[i]=2*a[floor(i/10)]+i%10

d=defaultdict(lambda:[])
i=1
x_to_decibin={}
for x,y in a.items():
    d[y].append(x)

i=1
l=list(d.values())
l=sum(l,[])

ind=[i for i in range(1,len(l)+1)]
x_to_decibin=dict(zip(ind,l))
print(x_to_decibin)
    
def decibinaryNumbers(x):
    return x_to_decibin[x]

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input().strip())

    for q_itr in range(q):
        x = int(input().strip())

        result = decibinaryNumbers(x)

        fptr.write(str(result) + '\n')

    fptr.close()

Answer 1

First there's some script cleanups I want to mention.

import math
import os
import random
import re
import sys
from math import floor
from collections import defaultdict

I'll assume that the imports from the default input may be needed, but I think it's pretty unnecessary to import floor in addition to math. Usually math.floor is short enough, but it's also not needed in this case.

a={0:0,1:1,2:2,3:3}

for i in range(4,10**6):
    a[i]=2*a[floor(i/10)]+i%10

Instead of using floor here, you can use a double division operator which will also do floored division. You also don't need a dict for this purpose, and could instead just initialize a list to the size you need.

N = 10**6+1 # Max size to compute (plus one for offset)

a = [0]*N

for i in range(1,N):
    a[i]=2*a[i//10]+i%10

---

d=defaultdict(lambda:[])
i=1
x_to_decibin={}
for x,y in a.items():
    d[y].append(x)

i=1
l=list(d.values())
l=sum(l,[])

The i=1 statements don't do anything here since i is overwritten when next used. x_to_decibin is also set later. The intermediate list is also unneeded since dict_values is iterable.

d=defaultdict(lambda:[])
# Iterate through decibin values (index) and add them to a list of their decimal value (element)
for index, element in enumerate(a):
    d[element].append(index)

l=sum(d.values(),[])

---

ind=[i for i in range(1,len(l)+1)]
x_to_decibin=dict(zip(ind,l))
print(x_to_decibin)

def decibinaryNumbers(x):
    return x_to_decibin[x]

I'm not sure if you included the print in a submission, but printing a fairly large structure won't be great. x_to_decibin also doesn't need to be created at all since you can just use l directly with a simple 1 offset.

def decibinaryNumbers(x):
    return l[x - 1] # Get value from precomputed list (with 1 offset)

With all of these changes, the running time for the setup with N=10**6+1 on my machine went from 5.7 to 2.4 seconds. From here, profiling shows that by far the slowest part of the script is calling sum on the large iterable. Replacing it with a itertools.chain.from_iterable call sped it up to 0.15 seconds.

However, I am only able to increase N to about 10**8 before memory starts becoming an issue. These changes allow for doing subtask 3 of 10**7 pretty quickly, but precomputing every value is just not going to work for the full size. If you want to do that, you'll instead need something that generates a value at runtime. You'll have to change your method to do this though. Try following some of what people have put in the discussions.

Final code:

from itertools import chain
from collections import defaultdict

N = 10**6+1

a = [0]*N

for i in range(1,N):
    a[i]=2*a[i//10]+i%10

d=defaultdict(lambda:[])
for index, element in enumerate(a):
    d[element].append(index)

l=tuple(chain.from_iterable(d.values()))

def decibinaryNumbers(x):
    return l[x - 1]