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.

#2652

Easy

auto_awesome数学·driven

LeetCode 题解工作台

倍数求和

给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3 、 5 、 7 整除的所有整数之和。返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。示例 1：输入： n = 7 输出： 21 解释：在 [1, 7] 范围内能被 3 、 5 、 7 整除的所有整数分别是 3 、 5 …

数学

题目描述

给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3、5、7 整除的所有整数之和。

返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。

示例 1：

输入：n = 7
输出：21
解释：在 [1, 7] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7 。数字之和为 21。

示例 2：

输入：n = 10
输出：40
解释：在 [1, 10] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9、10 。数字之和为 40。

示例 3：

输入：n = 9
输出：30
解释：在 [1, 9] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9 。数字之和为 30。

提示：

1 <= n <= 10³

lightbulb

解题思路

方法一：枚举

我们直接枚举 $[1,..n]$ 中的每一个数 $x$ ，如果 $x$ 能被 $3$ , $5$ , $7$ 整除，那么就将 $x$ 累加到答案中。

枚举结束后，返回答案即可。

时间复杂度 $O(n)$ ，其中 $n$ 为题目给定的整数。空间复杂度 $O(1)$ 。

1

2

3

4

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2651 计算列车到站时间 #2654 使数组所有元素变成 1 的最少操作次数 #2681 英雄的力量