Spoiler alert: This post contains spoilers for Project Euler.
Problem 1
Sum of the multiples of 3 or 5 below 1000
JS Solution 1
This is probably the first solution most people will think of. Simply go through each number and check if it is divisible by 3 or 5.
Modify the code and/or the timeout as you like. Infinite loops will hang your browser.JS Solution 2
We can skip the modulo check entirely and get a speedier solution.
Use two for loops - one increments by 3 and the other by 5. We will need to subtract the numbers that are divisible by both 3 and 5 to avoid double counting. One way to do that is with a third for-loop that increments by 15.
The number space that's explored will then be:
.
So only 60% of the numbers are visited with this solution. Making this a 0.6*O(n) solution.
If we wanted to be even more efficient (compute-wise) we could keep a counter that skips every 3rd number in the +5 increment. Or we could skip any numbers that end in 0 or 5 in the +3 increment.
Conclusion
If you run both solutions with a bigger ceiling, e.g., i = 1,000,000, you should notice that the 2nd solution is consistently a bit faster.