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.
The Task:
Find the sum of all natural numbers from 5 to 100000000 (100 million)
Solution 1
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.
Solution 2
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
Top comments (1)
Almost any regularly increasing range of numbers can be generalized like this!
Not all are super obvious, but if you see something like this in a coding challenge, figure out the equation (the above is sum(x)) and then try it out on wolframalpha.com