Skip to content

2652. Sum Multiples

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:

  • 1 <= n <= 103

Solutions

Solution 1: Enumeration

Thinking

Sum integers in \([1,n]\) divisible by \(3\), \(5\), or \(7\). \(n \le 1000\) allows scanning every \(x\) and testing those moduli.

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)

Thinking

Solution 1 scans \(n\) linearly. Multiples of \(x\) form an arithmetic series with a closed sum; inclusion-exclusion removes overlaps in \(O(1)\).

The value is \(f(3)+f(5)+f(7)-f(15)-f(21)-f(35)+f(105)\).

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
6
7
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

Thinking

The same inclusion-exclusion formula as Solution 2, rewritten in Rust; the algorithm and constants do not change.

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

Comments