LM10 - 1 year ago 225

C++ Question

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 Source

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.

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.