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