Project Euler Solutions

Problem 1

Problem 1: Find the sum of all multiples of 3 or 5 below n

There are two approaches an O(n) (Linear Time Complexity, time grows with input size, doubling the input size roughly doubles execution time) and an O(1) (Constant time complexity, input size doesn't matter)

Linear Time O(n), iterates through all numbers

function multiplesOf3Or5(number) {
    let sum = 0;
    for (let i = 0; i < number; i++) {
        if (i % 3 === 0 || i % 5 === 0) {
            sum += i;
        }
    }
    return sum;
}
console.log(multiplesOf3Or5(1000)); // 233168
                    

Constant Time O(1), directly calculates with a formula This function finds the sum of one multiple

function sumDivisibleBy(multiple, n) {
    let p = Math.floor((n - 1) / multiple);
    return multiple * (p * (p + 1)) / 2;
}
console.log(sumDivisibleBy(3, 1000)); // 166833
                        

This function adds up the sum of each multiple and then subtracts common multiples, to prevent double counting, since we are adding up the multiples, we dont want to add up numbers that repeat twice

function efficientSumMultiples(n) {
    return sumDivisibleBy(3, n) + sumDivisibleBy(5, n) 
    - sumDivisibleBy(15, n);
}
console.log(efficientSumMultiples(1000)); // 233168