Sum Multiples

EASY

Description

Given a positive integer n, find the sum of all integers in the range [1, n] inclusive that are divisible by 3, 5, or 7.

Return an integer denoting the sum of all numbers in the given range satisfying the constraint.

Example 1:

Input: n = 7
Output: 21
Explanation: Numbers in the range [1, 7] that are divisible by 3, 5, or 7 are 3, 5, 6, 7. The sum of these numbers is 21.

Example 2:

Input: n = 10
Output: 40
Explanation: Numbers in the range [1, 10] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9, 10. The sum of these numbers is 40.

Example 3:

Input: n = 9
Output: 30
Explanation: Numbers in the range [1, 9] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9. The sum of these numbers is 30.

Constraints:

1 <= n <= 10³

Approaches

Checkout 2 different approaches to solve Sum Multiples. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This is the most straightforward approach. We iterate through each number in the given range [1, n] and check if it's divisible by 3, 5, or 7. If it is, we add it to a running total. This method is easy to understand but less efficient for very large values of n.

Algorithm

Initialize a variable totalSum to 0.
Iterate with a loop variable i from 1 to n (inclusive).
Inside the loop, check if i is divisible by 3, 5, or 7 using the condition: i % 3 == 0 || i % 5 == 0 || i % 7 == 0.
If the condition is true, add i to totalSum.
After the loop finishes, return totalSum.

The algorithm works by initializing a sum variable to zero. It then enters a loop that goes from 1 to n. In each iteration, it checks if the current number i is divisible by 3, 5, or 7. The divisibility check is performed using the modulo operator (%). If i % 3 == 0 or i % 5 == 0 or i % 7 == 0, the number i is added to the sum. After checking all numbers up to n, the final sum is returned.

class Solution {
    public int sumOfMultiples(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                sum += i;
            }
        }
        return sum;
    }
}

Complexity Analysis

Time Complexity: O(n) - The algorithm iterates through all `n` numbers once. For each number, it performs a constant number of checks and an addition, making the time complexity linear with respect to `n`.Space Complexity: O(1) - The space required does not grow with the input size `n`. We only use a few variables to store the sum and the loop counter.

Pros and Cons

Pros:

Simple to understand and implement.
Guaranteed to be correct.
Sufficiently fast for the given constraints (n <= 1000).

Cons:

Inefficient for very large values of n as it performs n iterations.

Code Solutions

Checking out 3 solutions in different languages for Sum Multiples. Click on different languages to view the code.

class Solution {
public
  int sumOfMultiples(int n) {
    int ans = 0;
    for (int x = 1; x <= n; ++x) {
      if (x % 3 == 0 || x % 5 == 0 || x % 7 == 0) {
        ans += x;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Sum Multiples

Patterns:

Math