Given a range of natural numbers, from 1 to 100 for example, find the sum of all the given numbers. Below, we will implement some solutions then solve this on a small set of number that will work on any size of numbers that are in order.
Find the sum of all natural numbers from 5 to 100000000 (100 million)
This solution will use a loop to iterate and add each number together to get the sum.
Carl Friedrich Gauss
In the 1700's, there's a famous mathematician named Gauss, discovered a pattern to find the sum of numbers in a series, such as 1 to 100. The formula is like this:
s = n(n+1) /2, where s is the sum, n is the last number, and 1 is the first number.
The runtime for this solution is in milliseconds!!
What happened here!!, there is just one line of code and the output is the same as the loop solution.
A more efficient solution
To understand this better, let's solve this with a small set of numbers: 1 to 10.
In the 1 to 10 case, we can divide this into 5 pairs like this:
(1+10), (2+9), (3+8), (4+7), (5+6)
Notice that the sum of each pair are equal, if we multiply a pair by 5, we get the sum of 1 to 10.
To solve this with any large number sets in order, we can say that:
1. Get the sum of a pair - (minimum + maximum).
2. Get the number of pairs - length/2.
3. Multiply step 1 && step 2 to get the sum.
Notice: If you are curious and play around with different number sets, please convert int to float to avoid the miscalculation with odd-length sets. Exp:
puts final_solution(5, 100000000).to_f