Ameen P - 5 months ago 12

C Question

**Problem statement:**

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^5

1 <= N <= 10^9

**Output Format:**

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

This is my code :

`#include <stdio.h>`

int main() {

long t,i,x;

scanf("%ld",&t);

long y[t];

for(i=0; i<t; i++) {

scanf("%ld",&x);

long j,k,sum= 0;

if(x<=3)

sum= 0;

else if(x<=5)

sum= 3;

else {

for(j=3; j<x; j+=3)

sum= sum + j;

for(j=5; j<x; j+=5)

if(j%3!=0)

sum = sum + j;

}

y[i] = sum;

}

for(i=0; i<t; i++) {

printf("%ld\n",y[i]);

}

return 0;

}

Answer

There is a solution with a time complexity of O(T):

Use the formula for sum of integers `1+2+3+...+n = n*(n+1)/2`

.

Also note that `3+6+9+...+(3*n) = 3*(1+2+3+...+n) = 3*n*(n+1)/2`

.

Figure out how many numbers divisible by 3 there are. Calculate their sum.

Figure out how many numbers divisible by 5 there are. Calculate their sum.

Figure out how many numbers divisible by 15 (=3*5) there are. Calculate their sum.

Total sum is `sum3 + sum5 - sum15`

. The numbers divisible by both 3 and 5 (hence by 15) are both in sum3 and in sum5, so unless we subtract sum15 they would be counted twice.

Note that the sum will overflow a 32 bit integer, so make sure you use a 64 bit integer type.