Ameen P Ameen P - 2 months ago 6
C Question

Why I'm getting 'terminated due to timeout' error in hackerrank? or how can i reduce the complexity of this code(given below)?

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.