CODEWITHSUNDEEP
pythonalgorithmlistfor-loop
Bob Marshall
Bob Marshall

Reputation: 453

Optimizing sum of numbers in a list range

I am trying to answer a question on an online judge, but I keep running into time limit problems. The main idea of the problem is to solve the sum of a list minus the sum of a sublist within that list. The full problem specifications can be seen here.

Here is my code:

import sys
lists = sys.stdin.read().strip().split('\n')

showScores = map(int, lists[1].split())
maximum = sum(showScores)
loops = map(int, lists[0].split())[1]

for i in range(2, loops+2):
    subList = lists[i].split()
    print maximum - sum(showScores[int(subList[0])-1 : int(subList[1])])

Is there a better algorithm for solving the problem? How should I approach this, considering I have to do up to 500,000 loops?

Upvotes: 3

Views: 1544

Answers (2)

Brent Washburne
Brent Washburne

Reputation: 13138

@IVlad gave a very helpful hint in his answer, and I'll take it one step further with examples. Any time you can pre-compute values before a loop, the faster the loop will execute. Running sum() on a slice will return the same value for the same slice every time, so pre-compute the sums before the loop.

If you generated a list of sums of the first a scores, it would look like this:

first = [0, 5, 11, 18, 26, 29, 33, 38, 44, 45, 47]

If you also generated a list of the sums of the last b scores, it would look like this:

last = [47, 42, 36, 29, 21, 18, 14, 9, 3, 2, 0]

Inside of your loop, you could then

print first[a-1] + last[b]

which is faster than taking a sum of a slice.

Upvotes: 2

IVlad
IVlad

Reputation: 43477

You can avoid calling sum for each query. No matter how efficient the slicing, you still need to iterate that range to compute its sum, under your current setting. So you need to optimize your algorithm, not the code.

If you have:

S[i] = sum of the first i numbers
     = a[0] + a[1] + ... + a[i]

Which you can compute in O(n):

S[i] = S[i - 1] + a[i]

How can you answer each query in O(1) by using S?

Hint: if you had to compute the sum of some interval [x, y], we'd use:

S[y] = a[0] + a[1] + ... + a[x] + ... + a[y]
S[x] = a[0] + a[1] + ... + a[x - 1] + a[x]

Upvotes: 3

Related Questions