problemeasyalgorithmsleetcode-2652leetcode 2652leetcode2652

Sum Multiples

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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.

Examples

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

  • 1 <= n <= 10^3

Solution

Method 1 – Inclusion-Exclusion Principle

Intuition

To avoid double-counting numbers divisible by more than one of 3, 5, or 7, use the inclusion-exclusion principle. Compute the sum of multiples for each, subtract sums for pairs, and add back the sum for the triple.

Approach

  1. For each divisor (3, 5, 7), compute the sum of all multiples up to n.
  2. Subtract the sum of multiples for each pair (35, 37, 5*7).
  3. Add back the sum of multiples for 357.
  4. Return the result.

Code

C++
class Solution {
public:
    int sumOfMultiples(int n) {
        auto sum = [&](int d) {
            int cnt = n / d;
            return d * cnt * (cnt + 1) / 2;
        };
        return sum(3) + sum(5) + sum(7) - sum(15) - sum(21) - sum(35) + sum(105);
    }
};
Go
func sumOfMultiples(n int) int {
    sum := func(d int) int {
        cnt := n / d
        return d * cnt * (cnt + 1) / 2
    }
    return sum(3) + sum(5) + sum(7) - sum(15) - sum(21) - sum(35) + sum(105)
}
Java
class Solution {
    public int sumOfMultiples(int n) {
        return sum(n, 3) + sum(n, 5) + sum(n, 7) - sum(n, 15) - sum(n, 21) - sum(n, 35) + sum(n, 105);
    }
    private int sum(int n, int d) {
        int cnt = n / d;
        return d * cnt * (cnt + 1) / 2;
    }
}
Kotlin
class Solution {
    fun sumOfMultiples(n: Int): Int {
        fun sum(d: Int): Int {
            val cnt = n / d
            return d * cnt * (cnt + 1) / 2
        }
        return sum(3) + sum(5) + sum(7) - sum(15) - sum(21) - sum(35) + sum(105)
    }
}
Python
class Solution:
    def sumOfMultiples(self, n: int) -> int:
        def sumd(d: int) -> int:
            cnt = n // d
            return d * cnt * (cnt + 1) // 2
        return sumd(3) + sumd(5) + sumd(7) - sumd(15) - sumd(21) - sumd(35) + sumd(105)
Rust
impl Solution {
    pub fn sum_of_multiples(n: i32) -> i32 {
        fn sum(n: i32, d: i32) -> i32 {
            let cnt = n / d;
            d * cnt * (cnt + 1) / 2
        }
        sum(n, 3) + sum(n, 5) + sum(n, 7) - sum(n, 15) - sum(n, 21) - sum(n, 35) + sum(n, 105)
    }
}
TypeScript
class Solution {
    sumOfMultiples(n: number): number {
        function sum(d: number): number {
            const cnt = Math.floor(n / d);
            return d * cnt * (cnt + 1) / 2;
        }
        return sum(3) + sum(5) + sum(7) - sum(15) - sum(21) - sum(35) + sum(105);
    }
}

Complexity

  • ⏰ Time complexity: O(1) — Only a constant number of arithmetic operations are performed.
  • 🧺 Space complexity: O(1) — Only a few variables are used.

Comments