LM10 LM10 - 3 months ago 50
C++ Question

c++ - hackerrank project euler #1 terminated due to timeout

There are many discussions on this topic. I went through them, but none helped.

The question seems fairly simple:


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.

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

Constraints 1≤T≤10^5 1≤N≤10^9


However, for two test cases, most probably the ones with a large input, my code results in terminated due to timeout.

Here is my code:

int main() {
unsigned long long int n,t;
unsigned long long int sum;
cin>>t;
while(t--)
{
sum=0;
cin>>n;
for(unsigned long long int i=3;i<n;i++){
if(i%3==0 || i%5==0){
sum+=i;
}
}
cout<<sum<<"\n";
}

return 0;
}


Why is it not working for large inputs even with unsigned long long int?

Answer

I suggest using two loops of addition and eliminating the expensive % operator.

Given that all the numbers that are divisible by 3 are also all the numbers that have the 3 added. So rather testing a number for divisibility by 3 and summing them, only sum the numbers that are multiples of 3.

For example:

for (int i = 0; i < n; i = i + 3)
{
  sum += i;
}

If you also include the loop for 5, you would have all the values summed.

Also, subtract the values that are multiples of 15.

On the other hand, applying a little algebra and calculus, you could simplify the formula, then implement it.

Some Analysis

The quantity of values divisible by 3 are less then N/3. So for N = 13, there are 4 multiples of 3: 3, 6, 9, 12. So the limit is N/3.

Breaking down algebraically, we see that the numbers for N = 13, are:

[1] (3 * 1) + (3 * 2) + (3 * 3) + (3 * 4)  

Factoring out the common multiplying of 3 yields:

[2]  3 * ( 1 + 2 + 3 + 4)

Looking at equation [2], this yields 3 * sum(1..N).

Using the formula for summation:

(x * (x + 1)) / 2

the equation can be simplified to:

[3] 3 * ( 4 * (4 + 1) ) / 2

Or replacing the total values by N/3 this formula comes out to:

[4] 3 * ((N/3) * ((N/3) + 1) ) / 2

The simplification of equation [4] is left as an exercise for the reader.

Comments