Multiples of 3 and 5

Problem

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Ans:- 233168 

def compute():
	ans = sum(x for x in range(1000) if (x % 3 == 0 or x % 5 == 0))
	return str(ans)


if __name__ == "__main__":
	print(compute())

programming version of Problem From HackerRank.com

If we list all the natural numbers below  10 that are multiples of  3 or 5 , we get 3,5,6 and 9 . The sum of these multiples is 23 .

Find the sum of all the multiples of  3 or 5 below N .

Input Format

First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N .

Constraints

  • 1 ⩽ T ⩽ 105
  • 1 ⩽ N ⩽ 109

Output Format

For each test case, print an integer that denotes the sum of all the multiples of 3 or 5  below N .

Sample Input

2
10
100

Sample Output

23
2318

Explanation

For N=10  , if we list all the natural numbers below 10  that are multiples of  3 or 5, we get  3,5,6 and 9 . The sum of these multiples is 23.

Similarly for N=100 , we get 2318 .

Approach:

  • We know that multiples of 3 form an AP as S3 = 3 + 6 + 9 + 12 + 15 + 18 + 21 + …
  • And the multiples of 7 form an AP as S5 = 5 + 10 + 15 + 20 + …
  • Now, Sum = S3 + S5 i.e. 3 + 5 + 6 + 9 +10+ 12 + 15+ 18 + 21 + …
  • From the previous step, 15 is repeated twice. In fact, all of the multiples of 15 (or 3*5) will be repeated as they are counted twice, once in the series S3 and again in the series S5. So, the multiples of 15 need to be discarded from the result.
  • So, the final result will be S3 + S5 – S15
    The formula for the sum of an AP series is :
    n * ( a + l ) / 2
    Where n is the number of terms, a is the starting term, and l is the last term.

Python3:-

t=int(input())
def ar(x):
    return x*(x+1);
for i in range(t):
    n =int(input())
    n -=1;
    a=int(n/3);
    b=int(n/5);
    c=int(n/15);
    print(int(int(3*ar(a) + 5*ar(b) - 15*ar(c))>>1));

 

This problem has Test Case 2 and 3 as very large inputs hence the complexity of the solution should not exceed O(n)

Other Solution with Complexity O(n2) are:-

Solution-1

def compute():
    ans = sum(x for x in range(n) if (x % 3 == 0 or x % 5 == 0))
    return str(ans)

t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    print(compute())

Solution:-2

S=[]
t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    K=0
    for i in range(n):
            if (i%3==0 or i%5==0):
                K=K+i
    print(K)