Back to questions
Write a function to find the sum of all multiples of 3 or 5 below a target value.
For example, if the target value was 10, the multiples of 3 or 5 below 8 are 3, 5, 6, and 9.
Because , our function would return 23.
Here's the Python solution:
We iterate through every number under the target, and check if it's divisible by 3 or 5. If it is, we add it to the running sum.
The runtime complexity of this algorithm is because we iterate through every number below the target. Pretty easy!
What makes this a fun Google interview question is the next part: can you get an answer that runs in constant time, and doesn't have to iterate through every number below the target?