The Gauss' Trick

Overview

A method for finding the sum of an arithmetic series in O(1) time.

Formula:

S = (n / 2) * (i + j);

• i: First term.
• j: Last term.
• n: Number of terms.

  n = (j - i) / d + 1;

  • d: Common difference (the step between terms).

    e.g., in 2, 4, 6, 8 the step is 2, so d = 2.

Examples

1. Sum of the numbers from 0 to 10:

   i = 0
   j = 10
   d = 1
   n = (10 - 0) / 1 + 1 = 11
   
   S = (11 / 2) * (0 + 10) = 5.5 * 10 = 55

2. Sum of the numbers from -5 to 2:

   i = -5
   j = 2
   d = 1
   n = (2 - (-5)) / 1 + 1 = 8
   
   S = (8 / 2) * ((-5) + 2) = 4 * (-3) = -12

3. Sum of the given numbers [2, 4, 6, 8, 10, 12, 14]:

   i = 2
   j = 14
   d = 2
   n = (14 - 2) / 2 + 1 = 7
   
   S = (7 / 2) * (2 + 14) = 3.5 * 16 = 56