Branch data Line data Source code
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 : 2 : 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 [  + ]: 2 : if (max < min)
43 : : {
44 : 0 : return 0;
45 : : }
46 : :
47 : 2 : return (int) ((max + min) * (double) (max  min + 1) / 2);
48 : : }
