Description Link to heading

2652. Sum Multiples (Easy)

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 <= 10³

Solution Link to heading

This problem can be solved with brute force due to the given small data range, but there are also non-bruteforce methods.

Another approach is to use the principle of inclusion-exclusion.

The desired result can be expressed as $3*\lfloor{\frac{n}{3}}\rfloor + 5*\lfloor{\frac{n}{5}}\rfloor + 7*\lfloor{\frac{n}{7}}\rfloor - 15*\lfloor{\frac{n}{15}}\rfloor - 21*\lfloor{\frac{n}{21}}\rfloor - 35*\lfloor{\frac{n}{35}}\rfloor + 105*\lfloor{\frac{n}{105}}\rfloor$.

This is because $3, 5, 7$ are coprime, so we can write it this way. Otherwise, the denominators in the latter part should be their least common multiple.

Code Link to heading 

class Solution {
public:
    int solve(int n, int k) {
        return k * (1 + n) * n / 2;
    }
    int sumOfMultiples(int n) {
        return solve(n / 3, 3) + solve(n / 5, 5) + solve(n / 7, 7) - solve(n / 15, 15) - solve(n / 21, 21) - solve(n / 35, 35) + solve(n / 105, 105);
    }
};