Sum of Integers Up to n Divisible by 3, 5, or 7
Company: Abridge
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
Given a positive integer `n`, return the sum of every integer in the range `[1, n]` that is divisible by at least one of 3, 5 or 7.
### Function Signature
```python
def sum_multiples(n: int) -> int:
```
### Rules
- Both ends of the range are included.
- An integer divisible by more than one of 3, 5 and 7 (such as 15 or 21) is added only once.
- If no integer in the range qualifies, return `0`.
### Constraints
- `1 <= n <= 1000`
- The answer is at most 500,500, so it fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: n = 21
Output: 140
```
The qualifying integers are 3, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20 and 21. Both 15 and 21 have two of the divisors but are added once each.
**Example 2**
```text
Input: n = 2
Output: 0
```
Neither 1 nor 2 is divisible by 3, 5 or 7.
**Example 3**
```text
Input: n = 12
Output: 52
```
The qualifying integers are 3, 5, 6, 7, 9, 10 and 12.
Overview: From an Abridge online assessment: given a positive integer n, return the sum of all integers from 1 to n that are divisible by 3, 5 or 7, adding numbers such as 15 or 21 only once. It tests precise handling of overlapping divisibility conditions and inclusive range boundaries.
Given a positive integer `n`, return the sum of every integer in the range `[1, n]` that is divisible by at least one of 3, 5 or 7.
**Rules**
- Both ends of the range are included.
- An integer divisible by more than one of 3, 5 and 7 (such as 15 or 21) is added only once.
- If no integer in the range qualifies, return `0`.
**Constraints**
- `1 <= n <= 1000`
- The answer is at most 500,500, so it fits in a 32-bit signed integer. It never exceeds 2^31 - 1, so `int` is sufficient in Java and C++.
**Example 1**
```text
Input: n = 21
Output: 140
```
The qualifying integers are 3, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20 and 21. Both 15 and 21 have two of the divisors but are added once each.
**Example 2**
```text
Input: n = 2
Output: 0
```
Neither 1 nor 2 is divisible by 3, 5 or 7, so the result is 0.
Constraints
- 1 <= n <= 1000
- The answer is at most 500,500, so it fits in a 32-bit signed integer (it never exceeds 2^31 - 1).
Examples
Input: (1,)
Expected Output: 0
Explanation: Minimum n; 1 is not divisible by 3, 5 or 7, so the sum is 0.
Input: (2,)
Expected Output: 0
Explanation: Largest n with no qualifying integer; the result is 0.
Hints
- Both ends of the range [1, n] are included, so n itself may qualify.
- A number such as 15 or 21 satisfies more than one of the divisibility conditions, yet it must be added to the sum only once.
- When no integer in the range qualifies, the answer is 0.