Leetcode | 2652. Sum Multiples | Easy | Java Solution
Sum Multiples - Video Solution
Watch 10 video solutions for Sum Multiples, a easy level problem involving Math. This walkthrough by Developer Docs has 1,118 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 <= 103
Approach Overview
Problem 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.
Complexity Analysis
| 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 |