EULER CODE - 1

QUESTION:-

[NB - For test cases and optimization checking go PROJECT EULER 1]

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≤10⁵
• 1≤N≤10⁹

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.

Ans:-

Though the question seems easy, this will give time limit error to most of your codes. Hence I am giving an optimized solution below in C++ and Python that passes all test cases.

C++ Code:-

#include<iostream> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long long int t; cin >> t; while(t--) { long long int n,sum1,sum2,sum3; cin >> n; long long int p=(n-1)/3,q=(n-1)/5,r=(n-1)/15; sum1 = 3*(p*(p+1)/2); sum2 = 5*(q*(q+1)/2); sum3 = 15*(r*(r+1)/2); cout << sum1+sum2-sum3 << endl; } return 0; }

Python Code:-

t = int(input())

for i in range(t):

    n = int(input())

    p = int((n-1)//3)

    q = int((n-1)//5)

    r = int((n-1)//15)

    sum = int(int((3*p*(p+1)//2))+int((5*q*(q+1)//2))-int((15*r*(r+1)//2)))

    print(sum)

Hope that helps, keep coding:)