015.md

2652. Sum Multiples

Difficulty: 🟢 Easy

Given a positive integer n, find the sum of all integers in the range [1, n] inclusive that is divisible by 3, 5, or 7. Return an integer denoting the sum of all numbers in the given range satisfying the constraint.

Examples:

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 <= 103

Solutions

Simple O(n)

Python3

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        total = 0
        for i in range(1, n+1):
            if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
                total += i
        return total
                

TypeScript

function sumOfMultiples(n: number): number {
    let total = 0;
    for(let i = 0; i <= n; i++) {
        if((i % 3 === 0) || (i % 5 === 0) || (i % 7 === 0)) {
            total += i;
        }
    }
    return total;
}

The given solution solves the problem by performing the following steps:

1. Initialize a variable total to 0 to keep track of the sum.
2. Iterate over the range from 1 to n+1.
3. In each iteration, check if the current number i is divisible by 3, 5, or 7 using the modulo operator %.
4. If i is divisible by any of the three numbers, add it to the total sum.
5. After the loop ends, return the final value of total, which represents the sum of all numbers in the range [1, n] that satisfy the constraint.

Complexity Analysis

The time complexity of this algorithm is O(n) because we iterate over the range from 1 to n once.

The space complexity of the algorithm is O(1) because we only use a constant amount of extra space to store the total variable.

Summary

The given solution calculates the sum of all integers in the range [1, n] that are divisible by 3, 5, or 7 by iterating over the range and checking each number for divisibility. It has a time complexity of O(n) and a space complexity of O(1), making it efficient for the given constraints.

NB: If you want to get community points please suggest solutions in other languages as merge requests.