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

import mathimport osimport randomimport reimport sysfrom math import floorfrom 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. Usuallymath.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 adict 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]*Nfor i in range(1,N):    a[i]=2*a[i//10]+i%10

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

Thei=1 statements don't do anything here sincei is overwritten when next used.x_to_decibin is also set later. The intermediate list is also unneeded sincedict_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 usel 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 withN=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 callingsum on the large iterable. Replacing it with aitertools.chain.from_iterable call sped it up to 0.15 seconds.

However, I am only able to increase N to about10**8 before memory starts becoming an issue. These changes allow for doing subtask 3 of10**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 chainfrom collections import defaultdictN = 10**6+1a = [0]*Nfor i in range(1,N):    a[i]=2*a[i//10]+i%10d=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]

• \$\begingroup\$I didn't understand what they did in the discussion section. I only want to optimize this code. Anything above 10^6 gives me memory error.\$\endgroup\$

  vijayalakshmi_bhagat

  – vijayalakshmi_bhagat

  2022-08-16 19:12:11 +00:00

  CommentedAug 16, 2022 at 19:12
• \$\begingroup\$Running it for 10^7 only used about 830MB on my machine, so I'd be a bit surprised to see aMemoryError there. You could try usingdel statements to deletea andd once done with them, and also usingarray.array('L') from thearray module instead of the current itereables fora,l, and and thedefaultdict lambda.\$\endgroup\$

  duckboycool

  – duckboycool

  2022-08-16 19:56:04 +00:00

  CommentedAug 16, 2022 at 19:56

• python
• python-3.x
• programming-challenge
• time-limit-exceeded
• number-systems