CODEWITHSUNDEEP
cperformancealgorithm
nc89
nc89

Reputation: 13

algorithm c sum multiples of 2 and 5

Days ago I had a job interview were they ask me how I would calculate the sum of all the numbers multiples of 2 or 5 from 1 to 10000 using a the c language. I did this:

int mult2_5()
{
     int i, sum=0;
     for(i = 1; i <= 10000; i++)
        if(i % 2 == 0 || i % 5 == 0)
          sum += i;
     return sum;  
}

I as wonder if it was any faster implementation that this one?

Upvotes: 1

Views: 456

Answers (5)

ldav1s
ldav1s

Reputation: 16305

Just work it out on paper first, if that's what you mean by "faster".

$2\sum_{1<=2k<=10000}k + 5\sum_{1<=5k<=10000} - 10\sum_{1<=10k<=10000}k$

Sorry, my SO equation-fu is weak...Anyway this route will give you something you can almost handle on paper: 5000*6001 after reducing a few steps

int
mult2_5(void)
{
    return 5000*6001;
}

Project Euler problem 1 is very similar. There's lots of folks who've posted their solution to this one.

Upvotes: 2

djechlin
djechlin

Reputation: 60788

This can just be done using math. Something like 2 * sum(1 to 5000) + 5 * sum(1 to 2000) - 10 * sum(1 to 1000). off-by-one errors left as exercise.

Upvotes: 1

chris
chris

Reputation: 412

I almost got to a pure and simple multiplication by doing a simple loop that starts with 35 (sum of 2 + 4 + 5 + 6 + 8 + 10) with a step of 60, as that's how much your result will increase by when you take the next lot e.g. 12 + 14 + 15 + 16 + 18 + 20 etc. for(int i=35;i<5976;i=i+60) { sum=sum+i } The 5976 comes from 5975 being the last row of numbers that end in 1000 i.e. 992 + 994 + 995 + 996 + 998 + 1000. So it turns out that this loop runs 100 times, increasing the sum by 35 the first turn and increasing by 60 the remaining 99 times. Which is now reducable to a simple multiplication or such.

Upvotes: 0

kallikak
kallikak

Reputation: 842

As mentioned in an earlier answer, explicitly looping through the relevant multiples is better than testing the remainder each loop. But it is not necessary to calculate the multiples of 10 and subtract. Just start at 5 and step by 10 to skip them all together.

int multiply2_5b(int max)
{
  int i, x2 = 0,x5 = 0;

  for (i = 2; i < max; i += 2)    x2 += i;    // Sum all multiples of 2   
  for (i = 5; i < max; i += 10)   x5 += i;    // Sum all odd multiples of 5

  return x2 + x5;
}

Upvotes: 2

dreamcrash
dreamcrash

Reputation: 51463

The modulus operator is inefficient. A more faster implementation would be something like this:

int multiply2_5(int max)
{
  int i, x2 = 0,x5 = 0,x10 = 0;

  for(i = 2; i < max; i+=2)    x2 += i;    // Store all multiples of 2   O(max/2)
  for(i = 5; i < max; i+=5)    x5 += i;    //  Store all multiples of 3  O(max/5)
  for(i = 10; i < max; i+=10)  x10 += i;   //   Store all multiples 10;  O(max/10)

  return x2+x5-x10;
}

In this solution I had to take out multiples of 10 because, 2 and 5 have 10 as multiple so on the second loop it will add multiples of 10 that already been added in the first loop; The three loops combine have O(8/10 max).

Another even better solution is if you take a mathematical approach.

You are trying to sum all numbers like this 2 + 4 + 6 + 8 ... 10000 and 5 + 10 + 15 +20 + ... 10000 this is the same of having 2 * (1 + 2 + 3 + 4 + … + 5000) and 5 * ( 1 + 2 + 3 + 4 + ... + 2000), the sum of 'n' natural number is (n * (n + 1)) (source) so you can calculate in a constant time, as it follows:

int multiply2_5(int max)
{
    // x = 2 + 4 + 6 + ... = 2 * (1 + 2 + 3 +...)
    // y = 5 + 10 + 15 + ... = 5 * (1 + 2 + 3 +...)
    // The sun of n natural numbers is sn = (n (n + 1)) / 2
   int x2 = max/ 2;                      // 2 * ( 1 +2 + 3 … max/2)
   int x5 = max /5;                      // 5 * ( 1 +2 + 3 … max/5)
   int x10 = max/ 10;                  
   int sn2 = 0.5 * (x2 * (x2+1));        // (n * (n + 1)) / 2
   int sn5 = 0.5 * (x5 * (x5+1)); 
   int sn10 = 0.5 * (x10 * (x10+1));
   return (2*sn2) + (5 *sn5) - (10*sn10);
}

Upvotes: 5

Related Questions