math – StellarRimz

Introduction

The sum of multiples of $k$ below $n$ is:

Formula:

$S_{k} = k \cdot \frac{m (m + 1)}{2}$

where $m = ⌊ \frac{n - 1}{k} ⌋$ .

Problem Statement:

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

For example:

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

Input Format

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

Constraints

1 <= T <= 10^5
1 <= N <= 10^9

Output Format

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

Sample Input 0

2
10
100

Sample Output 0

23
2318

Explanation 0

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

Solution:

#!/bin/python3
import sys
t = int(input().strip())
if 1 <= t <= pow(10,5):
    def sum_of_multiples(k, limit):
        m = (limit - 1) // k
        return k * m * (m+1) // 2
        
    for a0 in range(t):
        n = int(input().strip())
        s3 = sum_of_multiples(3, n)
        s5 = sum_of_multiples(5, n)
        s15 = sum_of_multiples(15, n)
        
        total = s3 + s5 - s15
        print(total)

Output:

Input (stdin)

Your Output (stdout)

23
2318

Expected Output

23
2318

Note:

Avoid using loops when solving this problem, as N can be large enough (about 10^9), which can cause time and space to explode. The trick is to use arithmetic series formulas.

import sys
t = int(input().strip())
if 1 <= t <= pow(10,5):
    for a0 in range(t):
        n = int(input().strip())
        total = 0
        # print("n = ", n)
        if 1 <= n <= pow(10,9):
            if n == 1:
                total = n
            li = [i for i in range(1, n) if (i%3 == 0 or i%5 == 0)]
            total = sum(li)
            print(total)

The above code has O(n) complexity; however, it fails under memory constraints. When used with the arithmetic formula, the time complexity becomes O(1).

Reference:

Contests | HackerRank