| 1 |
/* |
| 2 |
* methods/gauss.c |
| 3 |
* |
| 4 |
* Calculate the sum of a given range of integer numbers. |
| 5 |
* |
| 6 |
* Somewhat of a more subtle way of calculation - and it even has a story |
| 7 |
* behind it: |
| 8 |
* |
| 9 |
* Supposedly during math classes in elementary school, the teacher of |
| 10 |
* young mathematician Gauss gave the class an assignment to calculate the |
| 11 |
* sum of all natural numbers between 1 and 100, hoping that this task would |
| 12 |
* keep the kids occupied for some time. The story goes that Gauss had the |
| 13 |
* result ready after only a few minutes. What he had written on his black |
| 14 |
* board was something like this: |
| 15 |
* |
| 16 |
* 1 + 100 = 101 |
| 17 |
* 2 + 99 = 101 |
| 18 |
* 3 + 98 = 101 |
| 19 |
* . |
| 20 |
* . |
| 21 |
* 100 + 1 = 101 |
| 22 |
* |
| 23 |
* s = (1/2) * 100 * 101 = 5050 |
| 24 |
* |
| 25 |
* A more general form of this formula would be |
| 26 |
* |
| 27 |
* s = (1/2) * (max + min) * (max - min + 1) |
| 28 |
* |
| 29 |
* which is used in the piece of code below to implement the requested |
| 30 |
* function in constant time, i.e. without dependencies on the size of the |
| 31 |
* input parameters. |
| 32 |
* |
| 33 |
*/ |
| 34 |
|
| 35 |
#include "gauss.h" |
| 36 |
|
| 37 |
|
| 38 |
int gauss_get_sum (int min, int max) |
| 39 |
{ |
| 40 |
/* This algorithm doesn't work well with invalid range specifications |
| 41 |
so we're intercepting them here. */ |
| 42 |
if (max < min) |
| 43 |
{ |
| 44 |
return 0; |
| 45 |
} |
| 46 |
|
| 47 |
return (int) ((max + min) * (double) (max - min + 1) / 2); |
| 48 |
} |