Fizz Buzz Sum [Google Python Interview Question]

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 $3 + 5 + 6 + 9 = 23$, 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 $O(n)$ 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?