Sum Multiples - Video Solutions

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.