Wake up and smell the algorithms: Part 1
This is the first part of a series of little posts on the Intermediate Algorithms on freeCodeCamp. The intermediate algorithms are pretty interesting but they have hints provided that lead you to a straightforward answer, which may lead you overlook different approaches that aren’t mentioned. So these posts will look a little closer at these problems and try some different approaches. Today we’ll be summing the numbers in a range — get hyped!
In this problem we’re given an array containing two values (both natural numbers) that indicate the beginning and end (both inclusive) of a range of natural numbers. We’re tasked with finding the sum of all the numbers in this range. There’s also a hint saying we should check out Array.reduce() so let’s look at a solution using that to start us off.
Reduce that Array
If we want to use reduce to return the sum of the range we’ll first need an array containing the range of numbers then we apply reduce to our array.
Now that we’ve got a working solution we smash cmd+enter on our keyboard to go to the next challenge…but wait.
Sequences may seem bland. They’re just a list of numbers but are the bees knees and they’ll transform this problem of using .reduce into something a little more fun. In our case our range is the sequence of natural numbers (counting numbers) from our low to our high.
Let’s consider the first test case for a second — sumAll([1,4]). For this case we could use the formula for the sum of the numbers 1..n which would be much preferable for two reasons: 1, it an O(1) solution instead of an O(n) solution (so it runs much faster); 2, it’s more fun. The problem is that we want a solution that allows our starting value to be any old natural number not just 1. Fortunately for us we can subtract the sum of two different sequences to get the sum of the sequence we’re looking for. If A = 1, 2, 3, 4, 5 and we want the sum of C where C = 3, 4, 5 we can subtract B where B = 1, 2 from A to get C. The same applies to their sums and so we can solve the problem like this.
Now that we’ve got a fun solution we smash cmd+enter on our keyboard to go to the next challenge…but wait.
Sum to N
Why does our sumToN work? My initial reaction to such formulas is, ‘Well, I don’t know — A (math) wizard did it.’ Shall we merely accept it’s truth because a wizard told us to? No, of course not — let’s dive deeper!
The explanation I originally heard of the sum to n formula was that one day a disgruntled teacher assigned Euler some punitive busy-work, ‘Euler go sum the numbers from 1 to 100’. After a few seconds of thinking about it Euler gave the sum as 5050. What Euler noticed that allowed him to further pester his poor teacher was that you could manipulate the sequence 1 to 100. Instead of continually adding up the numbers from left to right he imagined adding the 1 to 100, 2 to 99 and so on. Doing it this way you’ll notice that the sums are the same (101) because after the first pair you are always taking one away from the high number and adding one to the low number. After this insight finding the solution is straightforward, we multiply the number of pairs by their value.
Fun story but where does that leave us? Well instead of just using the formula handed down to us we can find our own formula using the method that Euler used to find the solution for the sum of 1 to 100.