2652. Sum Multiples

Problem Description

Given a positive integer n, the task is to calculate the sum of all integers within the range from 1 to n (both inclusive) which are divisible by either 3, 5, or 7. Intuitively, this involves finding all the multiples of 3, multiples of 5, and multiples of 7 within that range, summing them up, and returning the result. A multiple of a number such as 3, 5, or 7 is any number that can be expressed as the product of that number and an integer. For example, 6 (2 * 3) and 15 (3 * 5) are multiples of both 3 and 5.

Intuition

The problem can be approached intuitively in two primary ways:

Intuition behind Solution 1: Enumeration (Brute Force)

The most straightforward approach is to enumerate, i.e., iterate through every number in the range from 1 to n and check which numbers are divisible by 3, 5, or 7. If a number is divisible by any of these, it gets added to a running sum. This method is not very efficient for large values of n because it requires checking every single number up to n, which means O(n) time complexity—linear time in relation to the size of the range.

Intuition behind Solution 2: Mathematics (Inclusion-Exclusion Principle)

A more mathematically elegant and efficient solution involves using the inclusion-exclusion principle to avoid enumerating through all numbers. This principle is a way to calculate the cardinality of the union of several sets—here, those sets are multiples of 3, 5, and 7. The principle accounts for the fact that some numbers are common multiples and thus would be counted more than once if we simply summed all multiples of 3, 5, and 7. To correct for this, we subtract the sums of pairs of multiples (the intersections of two sets) and then add back in the sum of numbers which are multiples of all three (the intersection of all three sets). By doing this, each multiple will be counted exactly once. This method reduces the problem to evaluating several arithmetic series, leading to a solution that runs in constant time, O(1), regardless of the size of n.

Learn more about Math patterns.

Solution Approach

Solution 1: Enumeration

The provided code snippet demonstrates the enumeration approach through a list comprehension in Python. The range(1, n + 1) function generates a sequence of numbers from 1 through n inclusive. The generator expression inside the sum function iteratively checks for each x in this range whether x % 3 == 0, x % 5 == 0, or x % 7 == 0, which are conditions for divisibility by 3, 5, and 7, respectively. If any of these conditions are true, x is included in the sum. This is essentially a brute force method that iterates through the entire range, checking each number individually.

The time complexity here is O(n), since each number up through n is looked at once. The space complexity is O(1) because only a single sum is being maintained and no additional space is required.

Solution 2: Mathematics (Inclusion-Exclusion Principle)

This solution deploys the inclusion-exclusion principle to find the required sum without having to iterate over the entire range. To implement this approach mathematically, we first define a function f(x) that can give us the sum of all multiples of x within the range [1, n]. To find the sum of these multiples, we note that they form an arithmetic sequence with x as the first term, the largest multiple of x less than or equal to n as the last term, and the number of terms being m = floor(n / x). Thus, the sum of an arithmetic series formula can be used to find f(x), which is f(x) = (x + mx) * m / 2.

To find the final sum of numbers divisible by 3, 5, or 7, we add up f(3), f(5), and f(7), and then subtract the sums of the numbers that are common multiples—which would have been counted multiple times—using f(3 * 5), f(3 * 7), and f(5 * 7). Lastly, we add back the sum of numbers that are divisible by 3, 5, and 7 (f(3 * 5 * 7)) to ensure they are counted once in the total sum, as the inclusion-exclusion principle dictates.

The entire sum can be expressed succinctly as:

f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7)

Here, the time complexity is O(1) because we are only performing a fixed number of arithmetic operations, and the space complexity remains O(1) as we are only calculating a sum with fixed terms and not storing multiple values.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate Solution 2, as it's the more mathematically involved approach. Consider the positive integer n = 10. We want to find the sum of all integers within the range from 1 to 10 (inclusive) that are divisible by 3, 5, or 7.

Firstly, we need to determine the arithmetic series for multiples of 3, 5, and 7 within our range. Given that the integer 10 is our limit:

The multiples of 3 are 3, 6, 9. The sum of these is 3 + 6 + 9 = 18.
The multiples of 5 are 5, 10. The sum of these is 5 + 10 = 15.
The multiples of 7 are 7, as 14 is beyond our range. The sum is 7.

Next, we account for the numbers that are multiples of both 3 and 5, both 3 and 7, and both 5 and 7 to avoid double-counting. Our range, however, is too small to have any common multiples for the latter two pairs, but for the multiples of both 3 and 5, we have:

The common multiples of 3 and 5 are simply 15 (as 30 is beyond our range), so this number is considered only once in the sum.

Finally, there are no numbers less than or equal to 10 that are multiples of 3, 5, and 7.

Hence, we can calculate the sum using the inclusion-exclusion principle as follows:

Add the sums of the multiples of 3, 5, and 7: 18 + 15 + 7 = 40.
Subtract the sum of the multiples of 3 and 5 to correct for double-counting: 40 - 15 = 25.
Since we don't have any multiples in our range that are common to 3 and 7 or 5 and 7, and there are no multiples of 3, 5, and 7, we do not subtract anything further.

The final sum of all integers within the range from 1 to 10 that are divisible by 3, 5, or 7 is 25.

This example demonstrates how even with a simple case, the inclusion-exclusion principle helps in accurately calculating the desired sum with minimal computational steps, adhering to an O(1) time complexity.

Solution Implementation

1class Solution:
2    def sum_of_multiples(self, n: int) -> int:
3        """
4        Calculate the sum of all multiples of 3, 5, or 7 up to and including a given number n.
5
6        :param n: The upper limit of the range within which to look for multiples.
7        :type n: int
8        :return: The sum of all multiples of 3, 5, or 7 up to and including n.
9        :rtype: int
10        """
11        # Use a generator expression within the sum function to iterate over all numbers from 1 to n (inclusive).
12        # Use the modulo operator (%) to check if the current number is a multiple of 3, 5, or 7.
13        # If the current number x is a multiple of any of those, it gets included in the sum.
14        return sum(x for x in range(1, n + 1) if x % 3 == 0 or x % 5 == 0 or x % 7 == 0)
15
16# Example usage:
17# sol = Solution()
18# result = sol.sum_of_multiples(10)
19# print(result)  # Output will be the sum of multiples of 3, 5, or 7 up to 10
20

1public class Solution {
2
3    // Method to calculate the sum of all multiples of 3, 5, or 7 up to and including the number n
4    public int sumOfMultiples(int n) {
5        // Initialize the accumulator variable for the sum
6        int sum = 0;
7        // Loop from 1 through n (inclusive)
8        for (int i = 1; i <= n; ++i) {
9            // Check if the current number i is a multiple of 3, 5, or 7
10            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
11                // Add the current number i to the sum if it is a multiple
12                sum += i;
13            }
14        }
15        // Return the resultant sum
16        return sum;
17    }
18}
19

1class Solution {
2public:
3    // Function to calculate the sum of multiples of 3, 5, or 7 up to a given number n.
4    int sumOfMultiples(int n) {
5        int sum = 0; // Initialize the sum to zero.
6      
7        // Loop from 1 to n (inclusive).
8        for (int i = 1; i <= n; ++i) {
9            // Check if the current number is a multiple of 3, 5, or 7.
10            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
11                sum += i; // Add the number to the sum if it's a multiple.
12            }
13        }
14      
15        // Return the calculated sum of the multiples.
16        return sum;
17    }
18};
19

1/**
2 * Calculates the sum of all multiples of 3, 5, or 7 up to and including number n.
3 * 
4 * @param {number} n - The upper limit for checking the multiples.
5 * @return {number} - The sum of the multiples of 3, 5, or 7 up to n.
6 */
7function sumOfMultiples(n: number): number {
8    // Initialize the answer variable that will store the sum of the multiples.
9    let sum = 0;
10
11    // Iterate through all numbers from 1 to n (inclusive).
12    for (let currentNumber = 1; currentNumber <= n; ++currentNumber) {
13        // Check if the current number is a multiple of 3, 5, or 7.
14        if (currentNumber % 3 === 0 || currentNumber % 5 === 0 || currentNumber % 7 === 0) {
15            // If it is a multiple, add the current number to the sum.
16            sum += currentNumber;
17        }
18    }
19
20    // Return the final sum after completing the loop.
21    return sum;
22}
23
24// Example usage:
25// const result = sumOfMultiples(10);
26// console.log(result); // This would output the sum of multiples of 3, 5, or 7 up to 10.
27

Time and Space Complexity

The provided code snippet computes the sum of all multiples of 3, 5, or 7 up to and including n.

The time complexity of this function is O(n), where n is the input to the function. This is because the code iterates through a range from 1 to n, checking each number to see if it is a multiple of 3, 5, or 7.
The space complexity is O(1) because no additional space is used that grows with the input size. The only space used is for the variable x during the iteration and temporary space for the sum function, which does not depend on the size of n.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know