1
\$\begingroup\$

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.

  #include <stdio.h>
  int main(){
    int i=0,j,k,l,sum=0;
    scanf("%d",&i);
    if(i<=100000&&i>0){
    for(j=0;j<i;j++){
        scanf("%d",&k);
        if(k<=1000000000&&k>0){
        for(l=3;l<k;l++){
            if(l%3==0||l%5==0)
                {sum+=l;}
        }}
    printf("%d\n",sum);
    sum=0;
    }}

The above code does satisfy all the test cases but it has been rejected citing that it is very slow. Please suggest improvements to the code.

\$\endgroup\$
  • 5
    \$\begingroup\$ The formatting makes it nearly unreadable. Code that doesn't look good also typically doesn't run well. \$\endgroup\$ – Edward Jul 8 '14 at 11:52
  • 2
    \$\begingroup\$ Hint: you don't need loops at all. How would you find out how many multiples of 3 (or 5, but let's stick with one term for the moment) there were? What stunt did Gauss do as a young student that's applicable? \$\endgroup\$ – Clockwork-Muse Jul 8 '14 at 12:30
  • 1
    \$\begingroup\$ possible duplicate of Finding the sum of all the multiples of 3 or 5 below 1000 \$\endgroup\$ – sds Jul 8 '14 at 15:27
  • \$\begingroup\$ @sds: That question is from a different user and about a different language. Such questions are not considered duplicates on Code Review. \$\endgroup\$ – Jamal Jul 8 '14 at 23:01
10
\$\begingroup\$

Generally, try to think about the problem before brute-forcing it.

Is there an easy way to sum all the multiples of 3 below \$N\$? Of course there is. First we note that the largest multiple of 3 is \$3 * \lfloor\frac{N}{3}\rfloor\$ and the sum of all the multiples is then \$3 * 1 + 3 * 2 + ... 3 * \lfloor\frac{N}{3}\rfloor\$. Factor out the 3 and you get \$3 * (1 + 2 + 3 + ... \lfloor\frac{N}{3}\rfloor)\$. Now we use Gauss's trick for summing the natural numbers to get a nice easy formula for the sum: \$3*x*\frac{x+1}{2}\$, where \$x\$ is \$\lfloor\frac{N}{3}\rfloor\$.

Similarly, we can get the sum for the multiples of 5, and add the results together. However, we then have a bunch of duplicates (namely multiples of 15) which we can also calculate in a similar manner and then subtract to get the final result.

This approach completely eliminates any and all looping, and so will be super quick.

Now, let's discuss your code. Here's a list of suggestions:

  1. If you are prompting the user, provide some helpful hints as to what you are expecting as input.

  2. Having hardcoded bounds such as yours is unintuitive. Have your sum be a long or even long long (depending on the desired platform) and you will not run into issues with integer inputs, which are guaranteed by scanf(%d). This will also cut down on the indentation, increasing readability.

  3. Variable names are important. While it is pretty easy to see that i, k are the bounds, and j, l are counter variables after reading the code, it would be even easier to understand with lower_bound, upper_bound and i, j for the counters (per standard practices).

  4. Consider generalizing the problem to create a function that will be reusable elsewhere.

\$\endgroup\$
1
\$\begingroup\$

You can solve it with one for loop. The % operator is predefined for numeric types to compute the remainder after division. So if the remainder after division is 0 then you can add "i" to "sum".

int sum = 0;
for(int i = 1; i < 1000; i++)
{
   int value1 = i%5 == 0?5:0;
   int value2 = i%3 == 0?3:0;
   sum += (value1 + value2) >0 ?i:0;
}
\$\endgroup\$
0
\$\begingroup\$

It's a very simple problem to get the answer. Just use the A.P and the answer will be:

(sum of multiple of 3) + (sum of multiple of 5) - (sum of multiple of 15)

Use this formula to calculate the sum = n(a + l) / 2, where n = number of terms.

  • a = first term
  • l = last term
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! This site is a bit different from the other Stack Exchange Q&A sites - here answers are expected to review the OP's code; please see what makes a good CR-ish answer on our Meta for more details. \$\endgroup\$ – Mathieu Guindon Jul 15 '15 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.