Harvindersingh Chavan - 1 month ago 5x

Python Question

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)
```

Source (Stackoverflow)

Comments