Educating Youngsters Programming – Sum the Multiples in a Vary utilizing Venn Diagram (Math and Bruteforce Algorithm)

Educating Youngsters Programming: Movies on Knowledge Buildings and Algorithms

Given a constructive integer n, discover the sum of all integers within the vary [1, n] inclusive which are divisible by 3, 5, or 7. Return an integer denoting the sum of all numbers within the given vary satisfying the constraint.

Instance 1:
Enter: n = 7
Output: 21
Clarification: Numbers within the vary [1, 7] which are divisible by 3, 5, or 7 are 3, 5, 6, 7. The sum of those numbers is 21.

Instance 2:
Enter: n = 10
Output: 40
Clarification: Numbers within the vary [1, 10] which are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9, 10. The sum of those numbers is 40.

Instance 3:
Enter: n = 9
Output: 30
Clarification: Numbers within the vary [1, 9] which are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9. The sum of those numbers is 30.

Constraints:
1 <= n <= 10^3

Sum the Multiples in a Vary utilizing Venn Diagram (Math and Bruteforce Algorithm)

Given the enter N is comparatively small, we are able to bruteforce it by checking every quantity between 3 to N inclusive and accumulate the quantity if it may be divisible by 3, 5 or 7. This resolution is O(N) time and O(1) house complexity.

1
2
3
4
5
6
7

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

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

This may be additionally written into one-liner.

1
2
3

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

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

We are able to visualize utilizing the Venn Diagram the place f(3) represents the sum of all of the numbers within the vary that may be divisible by 3, and related for f(5) and f(7).

Venn Diagram (Sum Multiples)

So the reply is Including F(5)+F(7)+F(3) and subtract their frequent intersections between any two, however then add the center half which is the frequent a part of three F(105).

The F perform could be carried out utilizing Brute Pressure Algorithm, which takes O(N) time by checking each integer between the vary [x, n] inclusive.

1
2
3
4
5
6
7
8
9

class Resolution:
    def sumOfMultiples(self, n: int) -> int:
        def f(x):
            ans = 0
            for i in vary(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 Resolution:
    def sumOfMultiples(self, n: int) -> int:
        def f(x):
            ans = 0
            for i in vary(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)

However it may be computed utilizing the Math – because the sum could be computed through for arithmetic development: a, a+d, a+second, a+3d, … a+nd.

1
2
3
4
5
6
7
8

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

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

This optimisation provides O(1) time/house optimum resolution.

–EOF (The Final Computing & Expertise Weblog) —

GD Star Score
loading…

694 phrases
Final Put up: Delayed Swap as a result of Numeric Underflow Bug by utilizing Tron’s triggerSmartContract Methodology
Subsequent Put up: Educating Youngsters Programming – Minimal Bit Flips to Convert Quantity (Hamming Distance)