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