Description#
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 by 3, 5, or 7 are 3, 5, 6, 7. The sum of these numbers is 21.
Example 2:
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 of these numbers is 40.
Example 3:
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 of these numbers is 30.
Constraints:
Solutions#
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.
After the enumeration, we return the answer.
The time complexity is $O(n)$, where $n$ is the given integer. The space complexity is $O(1)$.
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)
|
1
2
3
4
5
6
7
8
9
10
11
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| 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;
}
};
|
1
2
3
4
5
6
7
8
| func sumOfMultiples(n int) (ans int) {
for x := 1; x <= n; x++ {
if x%3 == 0 || x%5 == 0 || x%7 == 0 {
ans += x
}
}
return
}
|
1
2
3
4
5
6
7
8
9
| function sumOfMultiples(n: number): number {
let ans = 0;
for (let x = 1; x <= n; ++x) {
if (x % 3 === 0 || x % 5 === 0 || x % 7 === 0) {
ans += x;
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| impl Solution {
pub fn sum_of_multiples(n: i32) -> i32 {
let mut ans = 0;
for x in 1..=n {
if x % 3 == 0 || x % 5 == 0 || x % 7 == 0 {
ans += x;
}
}
ans
}
}
|
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}$.
According to the inclusion-exclusion principle, we can obtain the answer as:
$$
f(3) + f(5) + f(7) - f(3 \times 5) - f(3 \times 7) - f(5 \times 7) + f(3 \times 5 \times 7)
$$
The time complexity is $O(1)$, and the space complexity is $O(1)$.
1
2
3
4
5
6
7
| class Solution:
def sumOfMultiples(self, n: int) -> int:
def f(x: int) -> int:
m = n // x
return (x + m * x) * m // 2
return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
private int n;
public int sumOfMultiples(int n) {
this.n = n;
return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7);
}
private int f(int x) {
int m = n / x;
return (x + m * x) * m / 2;
}
}
|
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
int sumOfMultiples(int n) {
auto f = [&](int x) {
int m = n / x;
return (x + m * x) * m / 2;
};
return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7);
}
};
|
1
2
3
4
5
6
7
| func sumOfMultiples(n int) int {
f := func(x int) int {
m := n / x
return (x + m*x) * m / 2
}
return f(3) + f(5) + f(7) - f(3*5) - f(3*7) - f(5*7) + f(3*5*7)
}
|
1
2
3
4
5
6
7
| function sumOfMultiples(n: number): number {
const f = (x: number): number => {
const m = Math.floor(n / x);
return ((x + m * x) * m) >> 1;
};
return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7);
}
|
1
2
3
4
5
| impl Solution {
pub fn sum_of_multiples(n: i32) -> i32 {
(1..=n).filter(|&x| (x % 3 == 0 || x % 5 == 0 || x % 7 == 0)).sum()
}
}
|
Solution 3#
1
2
3
4
5
6
7
8
9
10
| impl Solution {
pub fn sum_of_multiples(n: i32) -> i32 {
fn f(x: i32, n: i32) -> i32 {
let m = n / x;
((x + m * x) * m) / 2
}
f(3, n) + f(5, n) + f(7, n) - f(3 * 5, n) - f(3 * 7, n) - f(5 * 7, n) + f(3 * 5 * 7, n)
}
}
|
