Sum Multiples — Solution in Python, Java & C++
Sum Multiples solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at TCS and Infosys.
Sum Multiples is an easy coding problem on math and number theory, asked in TCS, Infosys and Accenture interviews.
- 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
Hints for Sum Multiples
Hint 1
A direct loop over
1..nis plenty at this size.Hint 2
Use
or, notand— a number qualifies if any of the three divides it.Hint 3
The closed form uses inclusion–exclusion over the three divisors and their products.
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
xfrom1ton. - If
x % 3 == 0orx % 5 == 0orx % 7 == 0, addxto 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)Java
public static int sumOfMultiples(int n) {
int total = 0;
for (int x = 1; x <= n; x++) {
if (x % 3 == 0 || x % 5 == 0 || x % 7 == 0) total += x;
}
return total;
}C++
int sumOfMultiples(int n) {
int total = 0;
for (int x = 1; x <= n; x++) {
if (x % 3 == 0 || x % 5 == 0 || x % 7 == 0) total += x;
}
return total;
}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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.