Sum of Multiples
Easy · rating 1050 · Math
Read an integer n. Print the sum of all positive integers below n that are divisible by 3 or 5.
Constraints: 1 ≤ n ≤ 106
Editorial
Approach
Add up every number below n divisible by 3 or 5. Use or, not addition of the two series, so multiples of 15 aren't double-counted. A closed-form via arithmetic series (inclusion–exclusion) runs in O(1), but a simple loop is fine for these bounds.
print(sum(i for i in range(n) if i % 3 == 0 or i % 5 == 0))Complexity
Time: O(n) for the loop, O(1) with the formula. Space: O(1).
Related problems
- Binary to Decimal — Medium
- Count Divisors — Easy
- Decimal to Binary — Medium
- RGB to Hex Color — Easy
- Account Balance — Easy
- Count Set Bits — Medium