Skip to content
Advertisement

Problem of “Memory limit exceeded” and “Time limit exceeded” in Python

I have a problem to solve on the online judge. Its solution is to make the sum of the integer for example input 4, so 1+2+3+4 the output 10. For another example, the input is 10, so get sum of 1 to 10 to get in the output 55 and so on.

But when I used a list to store numbers and make sum(List), it gave me a “Memory limit exceeded”.

Here is the code:

n = int(raw_input())
lista = []
for x in range(1, n+1):
   lista.append(x)
print sum(lista)

I tried another solution not to save in a list to avoid the memory exceeded, so I tried this:

n = int(raw_input())
sum = 0
for i in xrange(1, n+1):
   sum = sum + i
print sum

But I get “Time limit exceeded”. What is the solution to this problem?

Note that the range of number to the input and it will test on is 1≤ N ≤ 10^9. When I try the 10^9, it takes a really long time to get the answer.

Another note is that the time limit per test is 1 second.

Advertisement

Answer

This is an arithmetic progression and computes as S = ½(a1 + an)n, where a1 is first member, which is 1 in this case. an is the last member which is n in this case.

def arthimPSum(n):
    return round((1 + n)*n *0.5)

print(arthimPSum(10**9))

Output

500000000500000000
Advertisement