Finally an O(1) Solution

I wrote a few bad solutions for Project Euler in PHP a while back and I figured it is time to go back and do it more efficiently, and in C++!

Problem 1 in O(1)!

So my first solution incremented variable i from 1 > n-1 each time testing if i was a multiple of 3 or 5 and adding to a total if it was. Fine… this works but O(n) doesn’t do too well if we’re testing cases up to say 10^9 plus PHP < 7.0 doesn’t like large integers without using bcmath.

So with a small amount of digging I found a simple arithmetic progression formula for calculating a sum of multiples (n/2)*(a+b) where a is the number in question b is the upper limit (highest number divisible by the number in question) and n is b divided by a.

So after running the sum of multiples below 1000 for 3:

(333/2) * (3+999) = 166.5 * 1002 = 166,833

And 5:

(199/2) * (5+995) = 99.5 * 1000 = 99,500

All you need to do is remove the sum of multiples that have been accounted for by 3 and 5. You can do this be subtracting the sum of multiples of 15:

(66/2) * (15+990) = 33 * 1005 = 33,165

From the sum of the previous two totals:

166,833 + 99,500 - 33,165 = 233,168

There you have it, with this in place my new solution achieves O(1), tested for any case up to and including 10^9.

It still doesn’t pass the Hacker Rank tests, wtf!?

The division by 2 causes a rounding error when using float or even long double so I had to find another formula, luckily there is another n*(x*(x+1)/2) where n is the number we’re searching for multiples of and x is the upper limit divided by n.

Here’s a link to my solution on Github.

Back