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?
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments