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.
Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?
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:
1f(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.
Which data structure is used to implement recursion?
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
3are3, 6, 9. The sum of these is3 + 6 + 9 = 18. - The multiples of
5are5, 10. The sum of these is5 + 10 = 15. - The multiples of
7are7, as14is beyond our range. The sum is7.
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
3and5are simply15(as30is 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, and7:18 + 15 + 7 = 40. - Subtract the sum of the multiples of
3and5to correct for double-counting:40 - 15 = 25. - Since we don't have any multiples in our range that are common to
3and7or5and7, and there are no multiples of3,5, and7, 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
201public 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}
191class 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};
191/**
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.
27What data structure does Breadth-first search typically uses to store intermediate states?
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), wherenis the input to the function. This is because the code iterates through a range from 1 ton, 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 variablexduring the iteration and temporary space for the sum function, which does not depend on the size ofn.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.