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

1
2
3

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

1
2
3

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

1
2
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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);
    }
};
1
2
3
4
5
6
7

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)
}
1
2
3
4
5
6
7
8
9

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;
    }
}
1
2
3
4
5
6
7
8
9

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)
    }
}
1
2
3
4
5
6

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)
1
2
3
4
5
6
7
8
9

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)
    }
}
1
2
3
4
5
6
7
8
9

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.