Sum Multiples
EasyPrompt
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:
[1, 7]Example 2:
[1, 10] that areExample 3:
[1, 9]
Constraints:
1 <= n <= 103
Approaches
2 approaches with complexity analysis and trade-offs.
This is the most straightforward approach. We iterate through each number in the given range [1, n] and check if it's divisible by 3, 5, or 7. If it is, we add it to a running total. This method is easy to understand but less efficient for very large values of n.
Algorithm
- Initialize a variable
totalSumto 0. - Iterate with a loop variable
ifrom 1 ton(inclusive). - Inside the loop, check if
iis divisible by 3, 5, or 7 using the condition:i % 3 == 0 || i % 5 == 0 || i % 7 == 0. - If the condition is true, add
itototalSum. - After the loop finishes, return
totalSum.
Walkthrough
The algorithm works by initializing a sum variable to zero. It then enters a loop that goes from 1 to n. In each iteration, it checks if the current number i is divisible by 3, 5, or 7. The divisibility check is performed using the modulo operator (%). If i % 3 == 0 or i % 5 == 0 or i % 7 == 0, the number i is added to the sum. After checking all numbers up to n, the final sum is returned.
class Solution { public int sumOfMultiples(int n) { int sum = 0; for (int i = 1; i <= n; i++) { if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) { sum += i; } } return sum; }}Complexity
Time
O(n) - The algorithm iterates through all `n` numbers once. For each number, it performs a constant number of checks and an addition, making the time complexity linear with respect to `n`.
Space
O(1) - The space required does not grow with the input size `n`. We only use a few variables to store the sum and the loop counter.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to be correct.
Sufficiently fast for the given constraints (n <= 1000).
Cons
Inefficient for very large values of
nas it performsniterations.
A highly efficient approach that uses a mathematical formula to calculate the sum in constant time. It's based on the Principle of Inclusion-Exclusion, which allows us to sum up multiples of 3, 5, and 7 while correctly handling overlaps (i.e., numbers divisible by more than one of these, like 15 or 21).
Algorithm
- Define a helper function
sumDivisibleBy(k, n)that calculates the sum of all numbers up tondivisible byk. - Inside the helper function, calculate the number of multiples
p = n / k. - Return the sum of the arithmetic series:
k * p * (p + 1) / 2. - In the main function, apply the Principle of Inclusion-Exclusion:
- Sum = (sum of multiples of 3) + (sum of multiples of 5) + (sum of multiples of 7)
-
- (sum of multiples of 15) - (sum of multiples of 21) - (sum of multiples of 35) -
+ (sum of multiples of 105) - Call the helper function for each of these divisors (3, 5, 7, 15, 21, 35, 105) and compute the final result.
Walkthrough
This method avoids looping entirely. The core idea is to calculate the sum of multiples for each number (3, 5, 7) individually, then subtract the sums of multiples of their pairs (15, 21, 35) to correct for overcounting, and finally add back the sum of multiples of all three (105) because it was subtracted too many times.
To find the sum of numbers up to n that are divisible by k, we can use the formula for an arithmetic progression. First, find the number of terms, p = n / k. The sum is k + 2k + ... + pk = k * (1 + 2 + ... + p). The sum of the first p integers is p * (p + 1) / 2. So, the sum of multiples of k is k * p * (p + 1) / 2.
We apply this formula for 3, 5, 7, 15, 21, 35, and 105 and combine the results using the inclusion-exclusion principle.
class Solution { public int sumOfMultiples(int n) { return sumDivisibleBy(3, n) + sumDivisibleBy(5, n) + sumDivisibleBy(7, n) - sumDivisibleBy(15, n) - sumDivisibleBy(21, n) - sumDivisibleBy(35, n) + sumDivisibleBy(105, n); } private int sumDivisibleBy(int k, int n) { int p = n / k; return k * p * (p + 1) / 2; }}Complexity
Time
O(1) - The solution involves a fixed number of arithmetic calculations. The runtime is constant and does not depend on the input `n`.
Space
O(1) - The space used is constant, as it only requires a few variables to store intermediate sums, regardless of the value of `n`.
Trade-offs
Pros
Extremely fast and efficient.
Scales to handle very large values of
nfar beyond the problem's constraints.
Cons
Requires knowledge of mathematical concepts (Inclusion-Exclusion Principle, Arithmetic Series).
The logic is less intuitive than a simple loop.
Solutions
Solution
class Solution {public int sumOfMultiples(int n) { int ans = 0; for (int x = 1; x <= n; ++x) { if (x % 3 == 0 || x % 5 == 0 || x % 7 == 0) { ans += x; } } return ans; }}class Solution {public: int sumOfMultiples(int n) { int ans = 0; for (int x = 1; x <= n; ++x) { if (x % 3 == 0 || x % 5 == 0 || x % 7 == 0) { ans += x; } } return ans; }};class Solution: def sumOfMultiples(self, 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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.