python powers of 2

general
,
1

def power(m,n,x):
temp=power(m,n/2,x)
if n%2 == 0:
return (temp%xtemp%x)%x
else:
return (mtemp%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

2

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

3

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

4

link of the prob:http://www.spoj.com/problems/FAST2/

5

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…:slight_smile:

6

hey but now the code gives tle :frowning:

7

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…:slight_smile:

8

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!!!

9

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

10

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

11

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 :frowning:

12

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
13

thanks a lot…

14

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