#2652

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Sum Multiples

Find the sum of integers divisible by 3, 5, or 7 in the range [1, n].

math

Problem Statement

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

Return the sum of these integers.

Examples

Example 1

Input: n = 7

Output: 21

Numbers in the range [1, 7] that are divisible by 3, 5, or 7 are 3, 5, 6, 7. The sum of these numbers is 21.

Example 2

Input: n = 10

Output: 40

Numbers in the range [1, 10] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9, 10. The sum of these numbers is 40.

Example 3

Input: n = 9

Output: 30

Numbers in the range [1, 9] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9. The sum of these numbers is 30.

Constraints

1 <= n <= 103

Solution Approach

Brute Force Approach

Iterate through each number from 1 to n and check if it is divisible by 3, 5, or 7. If true, add it to the sum.

Mathematical Summation

Use arithmetic progression to find the sum of multiples of 3, 5, and 7 up to n. Subtract duplicates where numbers are divisible by more than one factor.

Efficient Approach Using Inclusion-Exclusion

Apply the inclusion-exclusion principle to avoid counting numbers divisible by multiple factors more than once, then sum the results.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute force approach runs in O(n) time, iterating through each number in the range. The mathematical and inclusion-exclusion approaches are more efficient, potentially reducing the time complexity to O(1) for calculating sums directly.

What Interviewers Usually Probe

Looks for understanding of basic divisibility rules.
Evaluates ability to optimize solutions using mathematical principles.
Assesses familiarity with inclusion-exclusion in combinatorics.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the solution with unnecessary loops.
Failing to account for duplicates when using the mathematical summation approach.
Using an inefficient brute force solution for larger inputs.

Follow-up variants

Consider adding additional divisors, such as 11 or 13, to test understanding of the inclusion-exclusion principle.
Change the range to [1, n^2] for larger n values and examine time complexity.
Add constraints that n can be as large as 10^6 and explore more efficient algorithms.

FAQ

What is the key approach for solving the Sum Multiples problem?

The most efficient approach involves using inclusion-exclusion to find the sum of multiples of 3, 5, and 7, ensuring duplicates are handled.

What is the time complexity of the brute force solution?

The brute force solution runs in O(n) time, iterating over all numbers in the range to check divisibility.

How can the inclusion-exclusion principle help in this problem?

Inclusion-exclusion helps to avoid counting numbers divisible by multiple divisors (e.g., both 3 and 5) more than once, ensuring correct results.

How do you deal with numbers divisible by multiple factors?

When using the mathematical summation or inclusion-exclusion methods, you subtract the sum of numbers divisible by both factors to avoid overcounting.

What makes this problem a math-driven solution?

This problem uses arithmetic progression and inclusion-exclusion to efficiently compute the sum of multiples, which is a key mathematical strategy.

terminal

Solution

Solution 1: Enumeration

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.

1

2

3

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)

Solution 2: Mathematics (Inclusion-Exclusion Principle)

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}$.

1

2

3

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)

Solution 3

#### Rust

1

2

3

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)

Continue Practicing

#2651 calculate delayed arrival time #2654 minimum number of operations to make all array elements equal to 1 #2681 power of heroes