Sum Multiples — Easy Problem & Solution

Given a positive integer n, return the sum of all integers in [1, n] that are divisible by 3, 5 or 7. Example 1 Example 2 Example 3 Constraints 1 <= n <= 1000

Difficulty: Easy
Topics: Math, Number Theory
Asked at: TCS, Infosys, Accenture
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a positive integer n, return the sum of all integers in [1, n] that are divisible by 3, 5 or 7.

Example 1

Input: n = 7
Output: 21
Explanation: 3 + 5 + 6 + 7 = 21.

Example 2

Input: n = 10
Output: 40
Explanation: 3 + 5 + 6 + 7 + 9 + 10 = 40.

Example 3

Input: n = 9
Output: 30

Constraints

1 <= n <= 1000

How to solve Sum Multiples

Test each candidate against the three divisors and add it when any one divides it. The arithmetic shortcut is inclusion–exclusion, which computes the same total in constant time.

Approach

Loop x from 1 to n.
If x % 3 == 0 or x % 5 == 0 or x % 7 == 0, add x to the total.

Why it works

The closed form is S(3) + S(5) + S(7) - S(15) - S(21) - S(35) + S(105), where S(d) sums the multiples of d up to n. That is inclusion–exclusion on the three divisibility events, and it agrees with the loop.

Complexity

Time — O(n), or O(1) with inclusion–exclusion
Space — O(1)

Pitfalls

Adding a number once per matching divisor double counts multiples of 15, 21, 35 and 105.
Summing S(3) + S(5) + S(7) without subtracting the overlaps makes exactly that mistake.

Reference solution

Python

def sumOfMultiples(n: int) -> int:
    return sum(x for x in range(1, n + 1) if x % 3 == 0 or x % 5 == 0 or x % 7 == 0)

JavaScript

var sumOfMultiples = function(n) {
    var total = 0;
    for (var x = 1; x <= n; x++) {
        if (x % 3 === 0 || x % 5 === 0 || x % 7 === 0) total += x;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue