# 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.