Given a positive integer n, find the sum of all integers in the range [1, n] inclusive that are divisible by 3, 5, or 7.
Return an integer denoting the sum of all numbers in the given range satisfying the constraint.
Example 1:
Input: n = 7 Output: 21 Explanation: Numbers in the range[1, 7]that are divisible by3,5,or7are3, 5, 6, 7. The sum of these numbers is21.
Example 2:
Input: n = 10 Output: 40 Explanation: Numbers in the range[1, 10] that aredivisible by3,5,or7are3, 5, 6, 7, 9, 10. The sum of these numbers is 40.
Example 3:
Input: n = 9 Output: 30 Explanation: Numbers in the range[1, 9]that are divisible by3,5, or7are3, 5, 6, 7, 9. The sum of these numbers is30.
Constraints:
1 <= n <= 103Problem Overview: Given an integer n, compute the sum of all numbers in the range [1, n] that are divisible by 3, 5, or 7. Any number divisible by at least one of these values contributes to the total.
Approach 1: Brute Force Iteration (O(n) time, O(1) space)
Scan every integer from 1 to n. For each value i, check divisibility using modulus operations: i % 3 == 0, i % 5 == 0, or i % 7 == 0. If any condition holds, add i to a running sum. The algorithm performs a constant number of checks per number, so the runtime grows linearly with n. Space usage stays O(1) since only a few variables are maintained. This approach is straightforward and easy to implement in any language, but it becomes inefficient if n is very large.
Approach 2: Formulaic Summation with Inclusion-Exclusion Principle (O(1) time, O(1) space)
This method avoids iteration by using arithmetic series formulas from math. First compute the sum of multiples of a number k up to n. If m = floor(n / k), the multiples are k, 2k, 3k ... mk. Their sum equals k * m * (m + 1) / 2. Compute this for 3, 5, and 7. However, numbers divisible by multiple values get counted more than once. Apply the inclusion-exclusion principle: subtract sums for lcm(3,5)=15, lcm(3,7)=21, and lcm(5,7)=35, then add back the triple overlap lcm(3,5,7)=105. Each term uses the same arithmetic progression formula, so the final result is computed in constant time with a few arithmetic operations.
Recommended for interviews: Start with the brute force iteration to show you understand the requirement and divisibility checks. Then optimize using the arithmetic series formula and inclusion-exclusion. Interviewers usually expect the constant-time mathematical solution because it demonstrates comfort with mathematical reasoning and eliminating unnecessary loops.
This approach involves iterating through each number from 1 to n and checking if it is divisible by either 3, 5, or 7. If it is, add this number to the sum. This is a straightforward approach which ensures we only consider numbers that are divisible by these values.
The code iterates through each integer i from 1 to n. For each i, it checks if i is divisible by 3, 5, or 7 (i.e., the remainder when i is divided by 3, 5, or 7 is zero). If true, i is added to the sum. Finally, the sum is returned.
Time Complexity: O(n) because we iterate through all numbers from 1 to n.
Space Complexity: O(1) because we only use a constant amount of space.
This approach leverages the principle of inclusion-exclusion to calculate the sum of multiples without iterating through every number from 1 to n. It exploits the summation formula for arithmetic series to compute the sum of multiples of 3, 5, or 7, and their intersections to avoid double counting.
Using inclusion-exclusion principle, 'sumMultiples' calculates the sum of all multiples of 3, 5, and 7 efficiently, considering overlaps. The helper function, 'sumDivisibleBy', calculates the sum of multiples of any 'k' using arithmetic series summation.
Time Complexity: O(1) since the calculations are constant-time after initial parameter evaluation.
Space Complexity: O(1)
We directly enumerate every number x in [1,..n], and if x is divisible by 3, 5, and 7, we add x to the answer.
After the enumeration, we return the answer.
The time complexity is O(n), where n is the given integer. The space complexity is O(1).
We define a function f(x) to represent the sum of numbers in [1,..n] that are divisible by x. There are m = \left\lfloor \frac{n}{x} \right\rfloor numbers that are divisible by x, which are x, 2x, 3x, cdots, mx, forming an arithmetic sequence with the first term x, the last term mx, and the number of terms m. Therefore, f(x) = \frac{(x + mx) times m}{2}.
According to the inclusion-exclusion principle, we can obtain the answer as:
$
f(3) + f(5) + f(7) - f(3 times 5) - f(3 times 7) - f(5 times 7) + f(3 times 5 times 7)
The time complexity is O(1), and the space complexity is O(1)$.
Rust
| Approach | Complexity |
|---|---|
| Brute Force Iteration | Time Complexity: O(n) because we iterate through all numbers from 1 to n. |
| Formulaic Summation with Inclusion-Exclusion Principle | Time Complexity: O(1) since the calculations are constant-time after initial parameter evaluation. |
| Enumeration | — |
| Mathematics (Inclusion-Exclusion Principle) | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Iteration | O(n) | O(1) | Simple implementation or when n is small |
| Formula + Inclusion-Exclusion | O(1) | O(1) | Best for interviews and large n where iteration is unnecessary |
Leetcode | 2652. Sum Multiples | Easy | Java Solution • Developer Docs • 1,023 views views
Watch 9 more video solutions →Practice Sum Multiples with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor