2652. Sum Multiples

Problem Description

You are given a positive integer n. Your task is to find the sum of all integers from 1 to n (inclusive) that are divisible by at least one of the numbers: 3, 5, or 7.

In other words, you need to:

Check every integer from 1 to n
If a number is divisible by 3 OR divisible by 5 OR divisible by 7, include it in the sum
Return the total sum of all such numbers

For example, if n = 10, the numbers that meet the criteria are:

3 (divisible by 3)
5 (divisible by 5)
6 (divisible by 3)
7 (divisible by 7)
9 (divisible by 3)
10 (divisible by 5)

The sum would be 3 + 5 + 6 + 7 + 9 + 10 = 40.

The solution uses a straightforward enumeration approach where it iterates through all numbers from 1 to n and checks if each number is divisible by 3, 5, or 7 using the modulo operator (%). If x % 3 == 0 or x % 5 == 0 or x % 7 == 0, then x is added to the sum.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The most direct way to solve this problem is to check each number individually. Since we need to find numbers divisible by 3, 5, or 7, we can simply test each number from 1 to n against these conditions.

The key insight is recognizing that this is an "OR" condition - a number needs to be divisible by at least one of the three numbers, not all of them. This means for each number x, we check:

Is x % 3 == 0? If yes, include it.
If not, is x % 5 == 0? If yes, include it.
If not, is x % 7 == 0? If yes, include it.

Since n is a positive integer and we're checking a finite range [1, n], a brute force approach is perfectly reasonable. We don't need any complex mathematical formulas or optimizations - just iterate through each number and apply the divisibility test.

The modulo operator (%) gives us the remainder when dividing. If x % k == 0, it means x is perfectly divisible by k with no remainder. This is the standard way to check divisibility in programming.

By using a generator expression with sum(), we can efficiently calculate the total in a single line of code, checking all three conditions with logical OR operators and accumulating only the numbers that satisfy at least one condition.

Learn more about Math patterns.

Solution Approach

The solution uses a straightforward enumeration approach to solve the problem. Let's walk through the implementation step by step:

Iterate through the range: We enumerate every number x in the range [1, n] inclusive. This is done using range(1, n + 1) which generates all integers from 1 to n.
Check divisibility conditions: For each number x, we check if it satisfies any of the three divisibility conditions:
- x % 3 == 0: checks if x is divisible by 3
- x % 5 == 0: checks if x is divisible by 5
- x % 7 == 0: checks if x is divisible by 7
These conditions are combined using the logical OR operator (or), meaning the number is included if it satisfies at least one of these conditions.
Calculate the sum: We use Python's built-in sum() function with a generator expression. The generator expression (x for x in range(1, n + 1) if x % 3 == 0 or x % 5 == 0 or x % 7 == 0) produces only the numbers that meet our criteria, and sum() adds them all together.

The entire solution is implemented in a single line:

return sum(x for x in range(1, n + 1) if x % 3 == 0 or x % 5 == 0 or x % 7 == 0)

This approach has a time complexity of O(n) since we check each number from 1 to n exactly once, and a space complexity of O(1) as the generator expression doesn't store all values in memory at once - it generates and processes them one at a time.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's walk through the solution with n = 15 to see how the algorithm works:

Step 1: Iterate through each number from 1 to 15

For each number x, we check if it's divisible by 3, 5, or 7:

x = 1: 1 % 3 = 1, 1 % 5 = 1, 1 % 7 = 1 → Not divisible by any → Skip
x = 2: 2 % 3 = 2, 2 % 5 = 2, 2 % 7 = 2 → Not divisible by any → Skip
x = 3: 3 % 3 = 0 ✓ → Divisible by 3 → Include (sum = 3)
x = 4: 4 % 3 = 1, 4 % 5 = 4, 4 % 7 = 4 → Not divisible by any → Skip
x = 5: 5 % 3 = 2, 5 % 5 = 0 ✓ → Divisible by 5 → Include (sum = 3 + 5 = 8)
x = 6: 6 % 3 = 0 ✓ → Divisible by 3 → Include (sum = 8 + 6 = 14)
x = 7: 7 % 3 = 1, 7 % 5 = 2, 7 % 7 = 0 ✓ → Divisible by 7 → Include (sum = 14 + 7 = 21)
x = 8: 8 % 3 = 2, 8 % 5 = 3, 8 % 7 = 1 → Not divisible by any → Skip
x = 9: 9 % 3 = 0 ✓ → Divisible by 3 → Include (sum = 21 + 9 = 30)
x = 10: 10 % 3 = 1, 10 % 5 = 0 ✓ → Divisible by 5 → Include (sum = 30 + 10 = 40)
x = 11: 11 % 3 = 2, 11 % 5 = 1, 11 % 7 = 4 → Not divisible by any → Skip
x = 12: 12 % 3 = 0 ✓ → Divisible by 3 → Include (sum = 40 + 12 = 52)
x = 13: 13 % 3 = 1, 13 % 5 = 3, 13 % 7 = 6 → Not divisible by any → Skip
x = 14: 14 % 3 = 2, 14 % 5 = 4, 14 % 7 = 0 ✓ → Divisible by 7 → Include (sum = 52 + 14 = 66)
x = 15: 15 % 3 = 0 ✓ → Divisible by 3 (also by 5) → Include (sum = 66 + 15 = 81)

Step 2: Return the final sum

Numbers included: 3, 5, 6, 7, 9, 10, 12, 14, 15 Final sum: 3 + 5 + 6 + 7 + 9 + 10 + 12 + 14 + 15 = 81

Note that number 15 is divisible by both 3 and 5, but we only count it once in our sum since we're using an OR condition.

Solution Implementation

1class Solution:
2    def sumOfMultiples(self, n: int) -> int:
3        """
4        Calculate the sum of all positive integers up to n that are divisible by 3, 5, or 7.
5      
6        Args:
7            n: The upper bound (inclusive) for checking multiples
8          
9        Returns:
10            The sum of all numbers from 1 to n that are divisible by 3, 5, or 7
11        """
12        # Initialize sum to accumulate multiples
13        total_sum = 0
14      
15        # Iterate through all numbers from 1 to n (inclusive)
16        for number in range(1, n + 1):
17            # Check if the number is divisible by 3, 5, or 7
18            if number % 3 == 0 or number % 5 == 0 or number % 7 == 0:
19                # Add the number to the total sum if it's a multiple
20                total_sum += number
21      
22        return total_sum
23

1class Solution {
2    /**
3     * Calculates the sum of all positive integers up to n that are divisible by 3, 5, or 7.
4     * 
5     * @param n The upper bound (inclusive) for checking multiples
6     * @return The sum of all numbers from 1 to n that are multiples of 3, 5, or 7
7     */
8    public int sumOfMultiples(int n) {
9        // Initialize the sum accumulator
10        int sum = 0;
11      
12        // Iterate through all numbers from 1 to n (inclusive)
13        for (int number = 1; number <= n; number++) {
14            // Check if the current number is divisible by 3, 5, or 7
15            if (number % 3 == 0 || number % 5 == 0 || number % 7 == 0) {
16                // Add the number to the running sum if it's a multiple of any target divisor
17                sum += number;
18            }
19        }
20      
21        // Return the total sum of all valid multiples
22        return sum;
23    }
24}
25

1class Solution {
2public:
3    /**
4     * Calculate the sum of all positive integers less than or equal to n
5     * that are divisible by 3, 5, or 7.
6     * 
7     * @param n The upper bound (inclusive) for numbers to check
8     * @return The sum of all multiples of 3, 5, or 7 within the range [1, n]
9     */
10    int sumOfMultiples(int n) {
11        int sum = 0;  // Initialize sum to store the result
12      
13        // Iterate through all numbers from 1 to n (inclusive)
14        for (int current = 1; current <= n; ++current) {
15            // Check if current number is divisible by 3, 5, or 7
16            if (current % 3 == 0 || current % 5 == 0 || current % 7 == 0) {
17                sum += current;  // Add to sum if it's a multiple of any target number
18            }
19        }
20      
21        return sum;  // Return the total sum
22    }
23};
24

1/**
2 * Calculates the sum of all positive integers up to n that are divisible by 3, 5, or 7
3 * @param n - The upper bound (inclusive) for checking multiples
4 * @returns The sum of all multiples of 3, 5, or 7 from 1 to n
5 */
6function sumOfMultiples(n: number): number {
7    // Initialize the sum accumulator
8    let sum: number = 0;
9  
10    // Iterate through all numbers from 1 to n (inclusive)
11    for (let currentNumber: number = 1; currentNumber <= n; currentNumber++) {
12        // Check if the current number is divisible by 3, 5, or 7
13        if (currentNumber % 3 === 0 || currentNumber % 5 === 0 || currentNumber % 7 === 0) {
14            // Add the current number to the sum if it's a multiple of any target divisor
15            sum += currentNumber;
16        }
17    }
18  
19    // Return the total sum of all valid multiples
20    return sum;
21}
22

Time and Space Complexity

Time Complexity: O(n)

The code iterates through all integers from 1 to n using a range function and generator expression. For each number x in this range, it performs constant-time operations (checking divisibility by 3, 5, and 7 using modulo operations). Since we examine each number from 1 to n exactly once, the time complexity is linear with respect to n, giving us O(n).

Space Complexity: O(1)

Although the code uses a generator expression with the sum() function, generators don't store all values in memory at once - they yield values one at a time. The sum() function accumulates the result using a single variable to maintain the running total. No additional data structures are created that scale with the input size n. Therefore, the space complexity is constant, O(1).

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

Common Pitfalls

1. Inefficiency for Large Values of n

The brute force approach checks every single number from 1 to n, which becomes inefficient when n is very large (e.g., n = 10^6 or greater). Each number requires up to 3 modulo operations, resulting in O(n) time complexity that can be slow for large inputs.

Solution: Use the Inclusion-Exclusion Principle with arithmetic progression formulas to calculate the sum in O(1) time:

def sumOfMultiples(self, n: int) -> int:
    def sum_multiples(k, n):
        # Sum of multiples of k up to n using arithmetic progression
        count = n // k
        return k * count * (count + 1) // 2
  
    # Apply inclusion-exclusion principle
    sum3 = sum_multiples(3, n)
    sum5 = sum_multiples(5, n)
    sum7 = sum_multiples(7, n)
    sum15 = sum_multiples(15, n)  # LCM(3,5)
    sum21 = sum_multiples(21, n)  # LCM(3,7)
    sum35 = sum_multiples(35, n)  # LCM(5,7)
    sum105 = sum_multiples(105, n)  # LCM(3,5,7)
  
    return sum3 + sum5 + sum7 - sum15 - sum21 - sum35 + sum105

2. Duplicate Counting Misconception

Beginners might incorrectly try to avoid "double counting" by using nested conditions or complex logic, not realizing that the OR operator already handles this correctly. For example, the number 15 (divisible by both 3 and 5) is only counted once.

Solution: Trust the OR operator - it naturally handles the case where a number is divisible by multiple values. The condition x % 3 == 0 or x % 5 == 0 or x % 7 == 0 will evaluate to True as soon as any condition is met, and the number is added to the sum exactly once.

3. Off-by-One Errors with Range

Using range(1, n) instead of range(1, n + 1) would exclude n from consideration, leading to incorrect results when n itself is divisible by 3, 5, or 7.

Solution: Always remember that Python's range(start, stop) excludes the stop value. To include n in the check, use range(1, n + 1).

4. Integer Overflow in Other Languages

While Python handles arbitrarily large integers automatically, implementing this in languages like C++ or Java might cause integer overflow for large values of n.

Solution: Use appropriate data types (e.g., long long in C++ or long in Java) when implementing in other languages, or consider using the mathematical formula approach which reduces the risk of overflow during intermediate calculations.

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