Scale Engineer

Sum Multiples

Easy
#2409Time: 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: 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.
Patterns
Math

Prompt

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:

[1, 7]

Example 2:

[1, 10] that are

Example 3:

[1, 9]

 

Constraints:

  • 1 <= n <= 103

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem