Coding questions · Abridge
Sum of Integers Up to n Divisible by 3, 5, or 7
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.
Function Signature
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
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
Input: n = 2
Output: 0
Neither 1 nor 2 is divisible by 3, 5 or 7.
Example 3
Input: n = 12
Output: 52
The qualifying integers are 3, 5, 6, 7, 9, 10 and 12.
Sum of Integers Divisible by 3, 5 or 7
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.
Approach
Scan every integer i from 1 to n inclusive and add i to a running total when i % 3 == 0, i % 5 == 0 or i % 7 == 0. Invariant: after processing i, total equals the sum of the qualifying integers in [1, i]. Each integer is visited exactly once and the three divisibility tests are combined with a single OR, so a number divisible by several of 3, 5 and 7 (15, 21, 35, 105, ...) contributes exactly once. The loop bound includes n itself, as the rules require. When nothing qualifies (n = 1 or n = 2) the total stays 0. An equivalent O(1) approach uses inclusion-exclusion: S(3) + S(5) + S(7) - S(15) - S(21) - S(35) + S(105), where S(k) = k * m * (m + 1) / 2 with m = n // k; omitting the + S(105) term undercounts once 105 is in range. The largest answer, at n = 1000, is 272066, well within a 32-bit signed integer.
- Time complexity: O(n)
- Space complexity: O(1)