LeetCode 2652 - Sum Multiples

The problem requires calculating the sum of all integers from 1 up to a given positive integer n that are divisible by 3, 5, or 7. In simpler terms, we need to consider each number in the range [1, n] and check if it is a multiple of any of these three numbers.

leetcodeeasymath

LeetCode Problem 2652

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem requires calculating the sum of all integers from 1 up to a given positive integer n that are divisible by 3, 5, or 7. In simpler terms, we need to consider each number in the range [1, n] and check if it is a multiple of any of these three numbers. If it is, we include it in the running total.

The input is a single integer n where 1 <= n <= 103, which is relatively small. The output is a single integer representing the sum of all qualifying numbers.

Key points include that n is always positive, so we do not need to handle zero or negative numbers. Edge cases could involve small values like n = 1 where no numbers are divisible by 3, 5, or 7, or larger numbers where multiple numbers are divisible by more than one of 3, 5, or 7 (e.g., 15, 21, 35), which we must avoid double-counting in our summation logic.

Approaches

The brute-force approach is straightforward. We iterate over each integer from 1 to n and check if it is divisible by 3, 5, or 7. If it is, we add it to a cumulative sum. This method works because every integer can be checked individually for divisibility, but it involves n checks and may be inefficient for very large n. However, given the constraints (n <= 103), this approach is acceptable.

The optimal approach leverages the inclusion-exclusion principle from combinatorics. Instead of checking every number individually, we calculate the sum of multiples of 3, 5, and 7 separately and then subtract the sums of numbers counted twice (like multiples of 15, 21, or 35) and add back numbers counted three times (like multiples of 105). This reduces the need for explicit iteration over every number and gives an exact sum using simple arithmetic formulas for the sum of an arithmetic sequence.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Iterates through all numbers 1 to n, checking divisibility and summing
Optimal O(1) O(1) Uses arithmetic series formulas and inclusion-exclusion to calculate the sum directly

Algorithm Walkthrough

  1. Identify the three divisors: 3, 5, and 7.
  2. For each divisor, compute the number of multiples less than or equal to n. This is floor(n / divisor).
  3. Compute the sum of multiples of a number using the arithmetic series formula: sum = divisor * k * (k + 1) / 2 where k is the number of multiples.
  4. Apply inclusion-exclusion: add sums of multiples of 3, 5, 7, subtract sums of multiples of combinations of two divisors (3_5=15, 3_7=21, 5_7=35), and add back sums of multiples of all three divisors (3_5*7=105) to correct for over-subtraction.
  5. Return the final sum.

Why it works: This method works because the sum of multiples formula correctly computes the sum of evenly spaced numbers. Inclusion-exclusion ensures each number is counted exactly once, even if it is divisible by multiple divisors.

Python Solution

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        def sum_multiples(k: int) -> int:
            count = n // k
            return k * count * (count + 1) // 2
        
        sum3 = sum_multiples(3)
        sum5 = sum_multiples(5)
        sum7 = sum_multiples(7)
        
        sum15 = sum_multiples(15)
        sum21 = sum_multiples(21)
        sum35 = sum_multiples(35)
        sum105 = sum_multiples(105)
        
        return sum3 + sum5 + sum7 - sum15 - sum21 - sum35 + sum105

This Python implementation defines a helper function sum_multiples to calculate the sum of multiples of a given number up to n. We compute sums for individual divisors, sums for pairwise combinations to subtract overcounted numbers, and finally sum for the triple combination to adjust for over-subtraction. The final return value combines these according to the inclusion-exclusion principle.

Go Solution

func sumOfMultiples(n int) int {
    sumMultiples := func(k int) int {
        count := n / k
        return k * count * (count + 1) / 2
    }

    sum3 := sumMultiples(3)
    sum5 := sumMultiples(5)
    sum7 := sumMultiples(7)

    sum15 := sumMultiples(15)
    sum21 := sumMultiples(21)
    sum35 := sumMultiples(35)
    sum105 := sumMultiples(105)

    return sum3 + sum5 + sum7 - sum15 - sum21 - sum35 + sum105
}

The Go implementation mirrors the Python version. It defines an inner function sumMultiples to compute the sum of multiples, calculates sums for individual and combined divisors, and applies the inclusion-exclusion principle to produce the final sum. Integer division is used in Go for count, just like Python's // operator.

Worked Examples

Example 1: n = 7

  1. Multiples of 3: 3, 6 → sum = 9
  2. Multiples of 5: 5 → sum = 5
  3. Multiples of 7: 7 → sum = 7
  4. Multiples of 3*5=15 → none → sum = 0
  5. Multiples of 3*7=21 → none → sum = 0
  6. Multiples of 5*7=35 → none → sum = 0
  7. Multiples of 3_5_7=105 → none → sum = 0
  8. Total sum = 9 + 5 + 7 - 0 - 0 - 0 + 0 = 21

Example 2: n = 10

  1. Multiples of 3: 3, 6, 9 → sum = 18
  2. Multiples of 5: 5, 10 → sum = 15
  3. Multiples of 7: 7 → sum = 7
  4. Multiples of 15, 21, 35, 105 → none → sum = 0
  5. Total sum = 18 + 15 + 7 = 40

Example 3: n = 9

  1. Multiples of 3: 3, 6, 9 → sum = 18
  2. Multiples of 5: 5 → sum = 5
  3. Multiples of 7: 7 → sum = 7
  4. Multiples of 15, 21, 35, 105 → none → sum = 0
  5. Total sum = 18 + 5 + 7 = 30

Complexity Analysis

Measure Complexity Explanation
Time O(1) Each sum computation is constant time using the arithmetic series formula
Space O(1) Only a few integer variables are used, no extra data structures

The complexity is constant because we do not iterate through all numbers in [1, n] and instead use direct arithmetic calculations. Space complexity is minimal because no arrays or lists are needed.

Test Cases

# Provided examples
assert Solution().sumOfMultiples(7) == 21  # Example 1
assert Solution().sumOfMultiples(10) == 40  # Example 2
assert Solution().sumOfMultiples(9) == 30  # Example 3

# Edge cases
assert Solution().sumOfMultiples(1) == 0  # No multiples
assert Solution().sumOfMultiples(3) == 3  # Only 3 is a multiple
assert Solution().sumOfMultiples(5) == 8  # 3 + 5
assert Solution().sumOfMultiples(15) == 60  # Includes multiple overlaps: 3,5,6,9,10,12,15
assert Solution().sumOfMultiples(103) == 3672  # Upper limit of n
Test Why
n = 7 Basic case with small range
n = 10 Verifies multiple numbers and summation
n = 9 Tests correctness of sum for non-round numbers
n = 1 Edge case: no multiples
n = 3 Edge case: only one multiple
n = 5 Edge case: overlapping multiples of 3 and 5
n = 15 Checks inclusion-exclusion with overlapping multiples
n = 103 Tests upper bound performance

Edge Cases

First, when n is smaller than the smallest divisor (3), the sum should be zero. This tests the lower boundary and ensures no negative or incorrect sums are returned. The algorithm handles this because integer division n // k will be zero.

Second, when n is exactly a multiple of one or more divisors,