Possible integer overflow in python

Question

I was completing hackerrank's project euler problem #1. I wrote a brute force solution to check my answer. It seems to be correct, except at the input of 10^9. I have been told that the correct answer is:

233333333166666668

I am returning:

233333333166666680

n = 1000000000
sum_of_multiples_3 = int((int((n-1)/3.0)+1) * (int((n-1)/3.0)/2.0) * 3)
sum_of_multiples_5 = int((int((n-1)/5.0)+1) * (int((n-1)/5.0)/2.0) * 5)
sum_of_multiples_15 = int((int((n-1)/15.0)+1) * (int((n-1)/15.0)/2.0) * 15)
print(sum_of_multiples_3 + sum_of_multiples_5 - sum_of_multiples_15)

There is no integer overflow in Python. You can have floating point rounding errors.. — Martijn Pieters
– Martijn Pieters, Commented Feb 11, 2015 at 7:42
My mistake. I was missing a zero from my n. Try running it again. — zetologos
– zetologos, Commented Feb 11, 2015 at 7:49

Martijn Pieters · Accepted Answer · 2015-02-11 08:39:49Z

5

You are using float division where integer division will do:

int((n-1)/3.0)

is better expressed as

(n-1)//3

e.g. use Python's floor division operator, don't use a float, then floor.

Using integer floor division won't run into rounding issues as you stretch floating point arithmetic beyond its limits.

You can see this rounding error happen when you push n large enough:

>>> n = 100000000
>>> int((int((n-1)/15.0)+1) * (int((n-1)/15.0)/2.0) * 15)
333333316666665
>>> ((n-1)//15+1) * ((n-1)//15//2) * 15
333333316666665
>>> n = 1000000000
>>> int((int((n-1)/15.0)+1) * (int((n-1)/15.0)/2.0) * 15)
33333333166666664
>>> ((n-1)//15+1) * ((n-1)//15//2) * 15
33333333166666665

The extra 1 there comes purely from the fact that you ran into the limits of floats:

>>> (int((n-1)/15.0)+1) * (int((n-1)/15.0)/2.0)
2222222211111111.0
>>> ((n-1)//15+1) * ((n-1)//15//2)
2222222211111111
>>> (int((n-1)/15.0)+1) * (int((n-1)/15.0)/2.0) * 15
3.3333333166666664e+16

I'm not sure why you keep subtracting one from n; that's not needed at all and leads to incorrect results. Perhaps you were trying to compensate for float rounding errors? The correct formulas are:

(((n // 3) + 1) * (n // 3)) // 2 * 3
(((n // 5) + 1) * (n // 5)) // 2 * 5
(((n // 15) + 1) * (n // 15)) // 2 * 15

giving me the correct output for any n:

>>> n = 1000000000
>>> sum_of_multiples_3 = (((n // 3) + 1) * (n // 3)) // 2 * 3
>>> sum_of_multiples_5 = (((n // 5) + 1) * (n // 5)) // 2 * 5
>>> sum_of_multiples_15 = (((n // 15) + 1) * (n // 15)) // 2 * 15
>>> sum_of_multiples_3 + sum_of_multiples_5 - sum_of_multiples_15
233333334166666668

I'd have used a function here to calculate multiples:

def sum_of_multiples(n, k):
    k_in_n = n // k
    return ((k_in_n + 1) * k_in_n) // 2 * k

so you can verify that it works by comparing to a brute-force sum:

>>> sum(range(0, 10000 + 1, 3)) == sum_of_multiples(10000, 3)
True
>>> sum(range(0, 10000 + 1, 5)) == sum_of_multiples(10000, 5)
True
>>> sum(range(0, 10000 + 1, 15)) == sum_of_multiples(10000, 15)
True

then use that to calculate the answer:

>>> sum_of_multiples(n, 3) + sum_of_multiples(n, 5) - sum_of_multiples(n, 15)
233333334166666668

edited Feb 11, 2015 at 8:39

answered Feb 11, 2015 at 8:03

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

zetologos Over a year ago

I get a different result with n = 200 when I do: (((n-1)//5)+1) * (((n-1)//5)/2.0) * 5 and when I do: (((n-1)//5)+1) * (((n-1)//5)//2) * 5

Martijn Pieters Over a year ago

@zetologos: don't subtract 1 from n, and don't divide by a floating point value. You want to floor the division, so use // 2

zetologos Over a year ago

That looks correct. But I need the result to be exclusive rather than inclusive. Example: print(sum([i for i in range(5, 200, 5)]))

Martijn Pieters Over a year ago

No, the Euler problem has n included.

zetologos Over a year ago

Perhaps, but the hackerrank version of it is exclusive. What change would have to be required to make it exclusive?

|

Collectives™ on Stack Overflow

Possible integer overflow in python

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related