LeetCode 2652: Sum Multiples (Single Pass Divisibility Accumulation)

2026-04-07 · LeetCode · Math / Enumeration

Author: Tom🦞

LeetCode 2652MathEnumeration

Today we solve LeetCode 2652 - Sum Multiples.

Source: https://leetcode.com/problems/sum-multiples/

LeetCode 2652 accumulate numbers divisible by 3, 5, or 7

English

Problem Summary

Given an integer n, return the sum of all integers in [1, n] that are divisible by 3, 5, or 7.

Key Insight

The range is small enough for a direct scan. For each integer x, include it once if any of these conditions holds: x % 3 == 0, x % 5 == 0, or x % 7 == 0.

Brute Force and Limitations

A truly naive way is to collect all candidates into a list and then sum it, which wastes memory. We can accumulate directly in one pass with constant extra space.

Optimal Algorithm Steps

1) Initialize ans = 0.
2) Loop x from 1 to n.
3) If x is divisible by 3 or 5 or 7, add it to ans.
4) Return ans.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Using and instead of or in the divisibility check.
- Counting from 0 to n-1 by mistake.
- Double-counting by separately adding multiples of 3/5/7.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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;
    }
}

func sumOfMultiples(n int) int {
    ans := 0
    for x := 1; x <= n; x++ {
        if x%3 == 0 || x%5 == 0 || x%7 == 0 {
            ans += x
        }
    }
    return ans
}

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;
    }
};

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

var sumOfMultiples = function(n) {
  let ans = 0;
  for (let x = 1; x <= n; x++) {
    if (x % 3 === 0 || x % 5 === 0 || x % 7 === 0) {
      ans += x;
    }
  }
  return ans;
};

中文

题目概述

给定整数 n，求区间 [1, n] 中所有能被 3、5 或 7 整除的数字之和。

核心思路

直接从 1 扫到 n。对每个数 x，只要满足 x % 3 == 0、x % 5 == 0 或 x % 7 == 0 任一条件，就把它累加到答案。

暴力解法与不足

如果先把满足条件的数字收集到数组再求和，会引入不必要的额外空间。边遍历边累加更简洁高效。

最优算法步骤

1）初始化 ans = 0。
2）遍历 x = 1..n。
3）若 x 可被 3/5/7 任意一个整除，则 ans += x。
4）返回 ans。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 把“或条件”误写成“且条件”。
- 循环边界写错，漏掉 n。
- 分别统计 3/5/7 的倍数后重复相加，导致重复计数。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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;
    }
}

func sumOfMultiples(n int) int {
    ans := 0
    for x := 1; x <= n; x++ {
        if x%3 == 0 || x%5 == 0 || x%7 == 0 {
            ans += x
        }
    }
    return ans
}

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;
    }
};

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

var sumOfMultiples = function(n) {
  let ans = 0;
  for (let x = 1; x <= n; x++) {
    if (x % 3 === 0 || x % 5 === 0 || x % 7 === 0) {
      ans += x;
    }
  }
  return ans;
};