Teaching Kids Programming – Sum the Multiples in a Range using Venn Diagram (Math and Bruteforce Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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^3

Sum the Multiples in a Range using Venn Diagram (Math and Bruteforce Algorithm)

Given the input N is relatively small, we can bruteforce it by checking each number between 3 to N inclusive and accumulate the number if it can be divisible by 3, 5 or 7. This solution is O(N) time and O(1) space complexity.

1
2
3
4
5
6
7

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

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

This can be also written into one-liner.

1
2
3

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

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

We can visualize using the Venn Diagram where f(3) represents the sum of all the numbers in the range that can be divisible by 3, and similar for f(5) and f(7).

Venn Diagram (Sum Multiples)

So the answer is Adding F(5)+F(7)+F(3) and subtract their common intersections between any two, but then add the middle part which is the common part of three F(105).

The F function can be implemented using Brute Force Algorithm, which takes O(N) time by checking every integer between the range [x, n] inclusive.

1
2
3
4
5
6
7
8
9

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        def f(x):
            ans = 0
            for i in range(x, n + 1):
                if i % x == 0:
                    ans += i
            return ans
        return f(3) + f(5) + f(7) - f(15) - f(35) - f(21) + f(105)

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        def f(x):
            ans = 0
            for i in range(x, n + 1):
                if i % x == 0:
                    ans += i
            return ans
        return f(3) + f(5) + f(7) - f(15) - f(35) - f(21) + f(105)

But it can be computed using the Math – as the sum can be computed via for arithmetic progression: a, a+d, a+2d, a+3d, … a+nd.

1
2
3
4
5
6
7
8

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        def f(x):
            low = x
            high = n // x * x
            cnt = (high - low) // x + 1
            return (low + high) * cnt // 2
        return f(3) + f(5) + f(7) - f(15) - f(35) - f(21) + f(105)

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        def f(x):
            low = x
            high = n // x * x
            cnt = (high - low) // x + 1
            return (low + high) * cnt // 2
        return f(3) + f(5) + f(7) - f(15) - f(35) - f(21) + f(105)

This optimisation gives O(1) time/space optimal solution.

–EOF (The Ultimate Computing & Technology Blog) —