How to Find the Sum of 1 to 100, and Its Variants

Everett Gaius's picture
Submitted by Everett Gaius on Sat, 05/02/2020 - 20:48

Legend has it that the German Mathematician, Carl Friedrich Gauss, who was an elementary student during the late 1700s, showed his teacher how quickly he summed up the numbers 1 to 100 by using a simple mathematical trick.

Centuries later, most programmers are still doing it the long way!

Normally, programmers implement the sum of any integers from 1 to N thru the following script:

int i, s;
for (i=1, s=0; i <= 100; i++) s += i;

However, this method takes O(N) Time Complexity. Gauss' method is much more efficient as it only takes O(1) to get the sum of any integer from 1 to N. His method was derived by adding the first and last digit of the series, the second digit and the second to the last, and so on and so forth. Any of the pairs resulted in 101. He also recognized that by pairing the series, there only 50 pairs from numbers 1 to 100, thus the sum would be 50 x 101 = 5050.

We can generalize the idea thru the following equations, giving us O(1) Time Complexity:

  •   S = 1 + 2     + 3 ...         + N - 2 + N - 1 + N
  • + S = N + N - 1 + N - 2 + ....  + 3     + 2     + 1     
  •  2S = N + 1 + N + 1 + N + 1 ... + N + 1 + N + 1 + N + 1
  •  2S = N x (N + 1)
  •  S  = N x (N + 1) / 2

We can modify's Gauss' method to let's say finding the sum of all even numbers from 1 to 100, by multiplying the series by 2 (expressed as m below) and and modifying the value of N to N / m (Important: / denotes integer division).

  •   N = N / m
  •   S = (m)1 + (m)2     + (m)3 ...          + m(N - 2) + m(N - 1) + mN
  • + S =  m N + m(N - 1) +  m(N - 2) + ....  +(m)3      +(m)2      +(m)1
  •   S =  m  +  2m      + 3m ...          + mN - 2m  + mN - m + mN
  • + S =  mN +  mN - m  + mN - 2m ....    + 3m       + 2m     + m       
  •  2S =  mN + m  + mN + m ....                      + mN + m + mN + m
  •  2S =  N(mN + m)
  •  S  =  N(mN + m) / 2

 

As an exercise to the reader and using what you have learned just now:

Find the sum of all the multiples of 3 and 5 below 1000. The solution can be found in the attached file below, but I recommend you do it first before checking the solution. I do not want to deny you of your AHA moment!

 

Attachments: 
File Multiples of 3 and 5.cpp

Tags: