Sum Multiples

We are given a positive integer ( n ), and we want to find the sum of all integers in the range ( [1, n] ) that are divisible by 3, 5, or 7. We can accomplish this by using a mathematical formula that makes use of the principle of inclusion-exclusion.

Approach

  1. Calculate Sum for Each Divisor: We need to find the sum of numbers divisible by 3, 5, and 7. We can do this by using the formula for the sum of the first ( k ) multiples of ( d ): [ \text{sum}(d, k) = d \times \frac{k \times (k + 1)}{2} ] Here, ( d ) is the divisor (3, 5, or 7), and ( k ) is the number of times ( d ) divides ( n ) (i.e., ( k = \left\lfloor \frac{n}{d} \right\rfloor )).

  2. Apply Inclusion-Exclusion Principle: To avoid counting numbers that are divisible by more than one of the divisors (3, 5, 7), we need to subtract the sum of numbers divisible by the least common multiples (LCM) of these divisors.

  3. Calculate Final Result: Sum the results from step 1 and then subtract the results from step 2.

Code

Here’s the Python code implementing the above approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        # Function to calculate the sum of first k multiples of d
        def sum_of_multiples(d, k):
            return d * k * (k + 1) // 2

        # Sum the multiples of 3, 5, and 7
        sum_3_5_7 = sum_of_multiples(3, n // 3) + sum_of_multiples(5, n // 5) + sum_of_multiples(7, n // 7)

        # Subtract the multiples of 15, 21, 35, and 105 (LCMs)
        sum_15_21_35_105 = sum_of_multiples(15, n // 15) + sum_of_multiples(21, n // 21) + sum_of_multiples(35, n // 35) - sum_of_multiples(105, n // 105)

        # Return final result
        return sum_3_5_7 - sum_15_21_35_105

Example

  • For n = 7, the function returns 21.
  • For n = 10, the function returns 40.

Complexity

The code executes in ( O(1) ) time, as it involves basic arithmetic operations, and uses ( O(1) ) extra space. This approach efficiently calculates the sum of numbers in the given range satisfying the constraint.