Harvindersingh Chavan Harvindersingh Chavan - 3 months ago 17
Python Question

HackerRank Project Puler #1

What is wrong with this code? It is not passing case 2 & 3 on HackerRank.

T=long(input())
while T>0:
N=long(input())
sum=0
for i in range (1,N):
if i%3==0 or i%5==0:
sum+=i
print (sum)
T-=1


I'm new in programming and can't figure out what I did wrong.

https://www.hackerrank.com/contests/projecteuler/challenges/euler001

Answer

There are couple of issues with the code. First since you're using long I guess you're running it on Python 2. On Python 2 range will generate a list and you'll run out of memory since problem description states that max N is 10^9. You could fix that problem by switching to xrange that returns xrange object instead.

If you make the change described above the second issue would be speed. Since max N is 10^5 you'd potentially have to iterate over 10^14 numbers which takes far too long. In order to fix the used algorithm needs to be changed. You can use formula n * (n + 1) * mul / 2 to calculate the sum of all multiples of mul in range 0...n. Then you solve a case by just adding the sum of multiples of 3 and 5 and subtract multiples of 15:

def sum_multiples(num, mul):
    n = num / mul
    return n * (n + 1) * mul / 2

for _ in xrange(int(raw_input())):
    num = int(raw_input()) - 1
    print sum_multiples(num, 3) + sum_multiples(num, 5) - sum_multiples(num, 15)