# python powers of 2

def power(m,n,x):
temp=power(m,n/2,x)
if n%2 == 0:
return (temp%xtemp%x)%x
else:
return (m
temp%x*temp%x)%x
t=int(input())
g=1298074214633706835075030044377087
while(t):
t=t-1
p=int(input())
print (power(2,p+1,g)-1)%g

the code when compiled gives runtime error …saying eof when reading a file…
plz… tell me how to overcome this … i’m new to python

see this link…ideone link…i just added the terminating condition as it was entering an infinite recursion which was creating the RE…hope this helps…

powers_of_2 = [str(1<<i) for i in range(500)]
t=int(input())
while(t):
t=t-1
p=int(input())
if(p==0):
print “1”
else:
print (powers_of_2[p+1]-1)%1298074214633706835075030044377087
hey… i’m done with precomputation … still that eof

how are you providing the input…i.e. in what format…can u give an example on ideone!!!

input is simply
first enter the no. of test cases… n then enter p … i.e the power of two to b calculated…

hey but now the code gives tle

i think TLE is caused because ur algo is O(log(n)) per test case…i.e. total time complexity is O(T*log(n))…instead precompute all the values which will take and then print the required values per test case with a complexity of O(1)…i.e. total complexity will be the time required to precompute…which takes linear time…which is lesser than the previous algo…hope this helps…

also avoid doing so many modulo operations as it is very slow…also python can handle large integers so lesser modulo operations will not lead to overflow!!!

o.k… i also thought the same …
but can u give me the syntax in python… how should i precompute… python is new to me

u can go through this site…http://www.python.org/about/gettingstarted/

this is your corrected solution…http://ideone.com/N8rnU3 . 2 mistakes…1 is improper indentation and second is the time complexity again…for every n u are calculating 2^n which makes the complexity even worse…O(n^2)!!!

1 Like

thanks a lot…

Fix the indentation ,avoid unnecessary type casting . In python 2.7 you can just use `input()` without type casting to take the integer input. Also `power_of_2` is a list of strings. So, the print statement inside the else block will raise a TypeError