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

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

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).

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 $tex_a04a11c4b3ca64afdf0fa511ecbce905 Teaching Kids Programming - Sum the Multiples in a Range using Venn Diagram (Math and Bruteforce Algorithm) algorithms Brute Force Algorithm math python teaching kids programming Venn Diagram youtube video$ 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.

GD Star Rating

694 words
Last Post: Delayed Swap due to Numeric Underflow Bug by using Tron’s triggerSmartContract Method

Source: Internet

We are offering free coding tuts

X