Sum Multiples

Difficulty: Easy | Acceptance: 85.90% | Paid: No Topics: Math

Given a positive integer n, find the sum of all numbers in the range [1, n] inclusive that are divisible by 3, 5, or 7.

• Examples
• Constraints
• Brute Force Iteration
• Mathematical Inclusion-Exclusion

Examples

Input: n = 7
Output: 21
Explanation: Numbers in the range [1, 7] that are divisible by 3, 5, or 7 are 3, 5, 6, 7. The sum is 21.

Input: n = 10
Output: 40
Explanation: Numbers in the range [1, 10] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9, 10. The sum is 40.

Input: n = 9
Output: 30
Explanation: Numbers in the range [1, 9] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9. The sum is 30.

Constraints

1 <= n <= 10^3

Brute Force Iteration

Intuition Iterate through every number from 1 to n and check if it is divisible by 3, 5, or 7. If it is, add it to the running total.

Steps

• Initialize a variable total to 0.
• Loop from i = 1 to n (inclusive).
• For each i, check if i % 3 == 0 or i % 5 == 0 or i % 7 == 0.
• If the condition is true, add i to total.
• Return total.

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        total = 0
        for i in range(1, n + 1):
            if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
                total += i
        return total

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Simple to implement and efficient enough for the given constraints (n ≤ 10³).

Mathematical Inclusion-Exclusion

Intuition We can calculate the sum of multiples for each divisor individually using the arithmetic series sum formula, then apply the inclusion-exclusion principle to handle overlaps (numbers divisible by multiple divisors like 15, 21, 35, 105).

Steps

• Define a helper function sumDiv(k) that calculates the sum of all multiples of k up to n. The count of multiples is m = n // k. The sum is k * m * (m + 1) / 2.
• Calculate the sum of multiples for 3, 5, and 7 individually.
• Subtract the sum of multiples for the Least Common Multiples (LCM) of pairs: 15 (3,5), 21 (3,7), and 35 (5,7) because they were counted twice.
• Add back the sum of multiples for the LCM of all three: 105 (3,5,7) because it was subtracted three times and added three times, effectively removing it completely.

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        def sum_div(k):
            m = n // k
            return k * m * (m + 1) // 2
        
        return sum_div(3) + sum_div(5) + sum_div(7) - sum_div(15) - sum_div(21) - sum_div(35) + sum_div(105)

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Optimal mathematical solution that performs a constant number of arithmetic operations regardless of input size.