CODEWITHSUNDEEP
python
Aayushi
Aayushi

Reputation: 1

Why is there so much difference in the execution time of the below two codes for the given problem?

QUESTION: You are given an array of n numbers and q queries. For each query you have to print the floor of the expected value(mean) of the subarray from L to R.

INPUT:

First line contains two integers N and Q denoting number of array elements and number of queries.

Next line contains N space seperated integers denoting array elements.

Next Q lines contain two integers L and R(indices of the array).

OUTPUT:

print a single integer denoting the answer.

:

1<= N ,Q,L,R <= 10^6

1<= Array elements <= 10^9

Sample Input:

5 3
1 2 3 4 5
1 3
2 4
2 5

Sample Output:

2 
3
3

CODE1:

n,q=map(int, input().split())

arr=list(map(int,input().split()))
for i in range(0,q):
    s=0
    b=input().split()
    L=int(b[0])-1
    R=int(b[1])-1
    d=R-L+1
    for j in range(L,R+1):
        s=s+arr[j]
    print(s//d)

CODE 1 takes 8.02 sec to execute.

CODE2:

m, n = map(int, input().split())
a = list(map(int, input().split()))
s = []
s1 = 0
for i in range(m):
    s1 += a[i]
    s.append(s1)
for i in range(n):
    x, y = map(int, input().split())
    if x == 1:
        print((s[y-1])//(y-x+1))
    else:
        print((s[y-1] - s[x-2])//(y-x+1))

while CODE2 takes only 3.1 sec to execute. why is that so? Please elaborate.

problem link

Upvotes: 1

Views: 80

Answers (2)

sahasrara62
sahasrara62

Reputation: 11228

this is because in code 1: you are calculating the mean for each value between l and r. by doing this operation of k queries you are calculating sum each time and then getting mean. So your complexity becomes (k queries*complexity of getting sum/mean)

in code 2 :

you are saving the consecutive sum in an array O(n)

and when calculate the mean of k queries you are calling the sum value till l and r element from that summed array, and then taking difference and calculating mean, so o(1) for each query. this is saving time for you.

Upvotes: 1

ngShravil.py
ngShravil.py

Reputation: 5048

The time complexity matters a lot. CODE1 is having two nested for loops, so it's time complexity is O(n^2), where as CODE2 is having two for loops, but in sequence, so the time complexity is O(n).

Upvotes: 0

Related Questions