# Sum Multiples
**Difficulty:** EASY
[External](https://leetcode.com/problems/sum-multiples)
Canonical: https://scaleengineer.com/dsa/problems/sum-multiples
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## 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._

**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`

# Approaches
## Brute Force Iteration
This is the most straightforward approach. We iterate through each number in the given range `[1, n]` and check if it's divisible by 3, 5, or 7. If it is, we add it to a running total. This method is easy to understand but less efficient for very large values of `n`.
**Time:** O(n) - The algorithm iterates through all `n` numbers once. For each number, it performs a constant number of checks and an addition, making the time complexity linear with respect to `n`. · **Space:** O(1) - The space required does not grow with the input size `n`. We only use a few variables to store the sum and the loop counter.
**Pros:** Simple to understand and implement.; Guaranteed to be correct.; Sufficiently fast for the given constraints (n <= 1000).
**Cons:** Inefficient for very large values of `n` as it performs `n` iterations.
### Explanation
The algorithm works by initializing a sum variable to zero. It then enters a loop that goes from 1 to `n`. In each iteration, it checks if the current number `i` is divisible by 3, 5, or 7. The divisibility check is performed using the modulo operator (`%`). If `i % 3 == 0` or `i % 5 == 0` or `i % 7 == 0`, the number `i` is added to the sum. After checking all numbers up to `n`, the final sum is returned.

```java
class Solution {
    public int sumOfMultiples(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                sum += i;
            }
        }
        return sum;
    }
}
```
### Algorithm
- Initialize a variable `totalSum` to 0.
- Iterate with a loop variable `i` from 1 to `n` (inclusive).
- Inside the loop, check if `i` is divisible by 3, 5, or 7 using the condition: `i % 3 == 0 || i % 5 == 0 || i % 7 == 0`.
- If the condition is true, add `i` to `totalSum`.
- After the loop finishes, return `totalSum`.

## Mathematical Approach using Inclusion-Exclusion Principle
A highly efficient approach that uses a mathematical formula to calculate the sum in constant time. It's based on the Principle of Inclusion-Exclusion, which allows us to sum up multiples of 3, 5, and 7 while correctly handling overlaps (i.e., numbers divisible by more than one of these, like 15 or 21).
**Time:** O(1) - The solution involves a fixed number of arithmetic calculations. The runtime is constant and does not depend on the input `n`. · **Space:** O(1) - The space used is constant, as it only requires a few variables to store intermediate sums, regardless of the value of `n`.
**Pros:** Extremely fast and efficient.; Scales to handle very large values of `n` far beyond the problem's constraints.
**Cons:** Requires knowledge of mathematical concepts (Inclusion-Exclusion Principle, Arithmetic Series).; The logic is less intuitive than a simple loop.
### Explanation
This method avoids looping entirely. The core idea is to calculate the sum of multiples for each number (3, 5, 7) individually, then subtract the sums of multiples of their pairs (15, 21, 35) to correct for overcounting, and finally add back the sum of multiples of all three (105) because it was subtracted too many times.

To find the sum of numbers up to `n` that are divisible by `k`, we can use the formula for an arithmetic progression. First, find the number of terms, `p = n / k`. The sum is `k + 2k + ... + pk = k * (1 + 2 + ... + p)`. The sum of the first `p` integers is `p * (p + 1) / 2`. So, the sum of multiples of `k` is `k * p * (p + 1) / 2`.

We apply this formula for 3, 5, 7, 15, 21, 35, and 105 and combine the results using the inclusion-exclusion principle.

```java
class Solution {
    public int sumOfMultiples(int n) {
        return sumDivisibleBy(3, n) + sumDivisibleBy(5, n) + sumDivisibleBy(7, n)
               - sumDivisibleBy(15, n) - sumDivisibleBy(21, n) - sumDivisibleBy(35, n)
               + sumDivisibleBy(105, n);
    }

    private int sumDivisibleBy(int k, int n) {
        int p = n / k;
        return k * p * (p + 1) / 2;
    }
}
```
### Algorithm
- Define a helper function `sumDivisibleBy(k, n)` that calculates the sum of all numbers up to `n` divisible by `k`.
- Inside the helper function, calculate the number of multiples `p = n / k`.
- Return the sum of the arithmetic series: `k * p * (p + 1) / 2`.
- In the main function, apply the Principle of Inclusion-Exclusion:
- Sum = (sum of multiples of 3) + (sum of multiples of 5) + (sum of multiples of 7)
-       - (sum of multiples of 15) - (sum of multiples of 21) - (sum of multiples of 35)
-       + (sum of multiples of 105)
- Call the helper function for each of these divisors (3, 5, 7, 15, 21, 35, 105) and compute the final result.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
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)

```