The Ultimate Guide to JavaScript Algorithms: Range Sum

Publikováno: 5.4.2019

Sometimes, while performing mathematical calculations, there comes the need to sum up a range of numbers. Some programming languages make this easy by implementing helper functions that enable one ...

Celý článek

In this challenge, we implement our own helper function for summing up numbers within a specified range. The range is specified using an array in the format:

[minimum,maximum]

You should already have your development environment setup for this course. Open the cloned repository and inside the Beginner folder, navigate to the rangeSum folder. Our work for this challenge will be done in here. Make sure to follow along in the index-START.js file.

The Challenge

Given an array of two numbers, return the cummulative sum of the two numbers and all the numbers between them. E.g

rangeSum([1,9]) 
// Should return 45 i.e 1+2+3+4+5+6+7+8+9

Algorithmic Thinking

We are to write a function that accepts one parameter i.e an array containing the minimum and maximum limit of the range respectively.

To solve this challenge, we need to sum up all the numbers as we loop through all the numbers starting from the minimum until we arrive at the maximum limit.

Pretty straightforward! Let’s do this!

Code Implementation

Let's now consider four ways to solve this challenge. They are:

Using a For-loop
Using the Arithmetic Progression Formula
Using Recursion
Using .reduce()
Using a For-Loop

In this approach, we use a For-loop to iterate through every value from the minimum arr[0] to the maximum arr[1].

function rangeSum(arr) {
  let sum = 0;
  for (i = arr[0]; i <= arr[1]; i++) {
    sum += i;
  }
  return sum;
}

Notice how we initialize an accumulator variable sum to 0 . With sum, we accumulate the sum by adding the current value of the iterator on every iteration. We basically start at the minimum value received and add every number we encounter to our sum until we arrive at the maximum number. At the end, we return sum as the final result.

Now let's try using a formula.

Using the Arithmetic Progression Formula

In mathematics, an arithmetic progression (AP) or arithmetic sequence is a sequence of numbers ordered such that the difference between the consecutive terms is constant. This simply means, a list of numbers where the difference between each number and the next is always the same. Notice that in a range as shown below, this applies.

1,2,3,4,5,6,7,8,9,...

In the sequence above, the common difference is 1 and this will remain the case no matter how much farther we extend the list. A general formula for calculating the sum of an arithmetic progression for a certain range of numbers with n number of elements is:

Formula for finding the sum of an Arithmetic Progression

a1 = First term of the sequence an = Last term of the sequence n = Number of elements in the sequence

In the solution below we apply this formula in solving the challenge.

function rangeSum(arr) {
  return ((arr[1] - arr[0] +1) * (arr[0] + arr[1])) / 2;
}

We derive the value of n as maximum limit - minimum limit + 1 as shown in the first bracket within the return statement. The rest of it follows accordingly, thus we arrive at the final sum which we return from the function.

Now let’s try recursion.

Using Recursion

In this solution we apply recursion by continually reducing the maximum limit and summing up all the returned values to arrive at the final sum.

function rangeSum(arr) {
  if (arr[0] == arr[1]) {
    return arr[0];
  } else {
    return rangeSum([arr[0], arr[1] - 1]) + arr[1];
  }
}

Notice that we first specify a terminating case such that as soon as the maximum and minimum limits are equal, the recursion terminates by returning the current minimum i.e arr[0].

A step by step analysis of what is going on above will reveal that while we continually reduce the value of the maximum limit by 1 for each recursive cycle i.e arr[1] -1, we sum up all the maximum limits up until the minimum limits equals the maximum limit. Thus, for rangeSum([1,9]), we would have:

9+8+7+6+5+4+3+2+1

Let’s consider one final approach.

Using .reduce()

To apply this method, we first need to generate an array containing all the numbers found within the specified range. Thus, we initialize a variable arrList with an empty array for this purpose. Using a for-loop, with our iterator i starting from the minimum value arr[0] we push every value of i into our arrList until we arrive at the maximum limit arr[1].

function rangeSum(arr) {
  let arrList = [];
  for (i = arr[0]; i <= arr[1]; i++) {
    arrList.push(i);
  }
  return arrList.reduce((acc, num) => acc + num, 0);
}

After successfully populating arrList, we call the .reduce() method on the array. Starting with 0 as the initial value of the accumulator, we add the current number num from the array list to the accumulator and then move on to the next. At the end of this process, the final value arrived at is the sum and is returned as such.

Wheeew!!! That was pretty tasking.

Testing

Testing correctness with Jest

To test the solutions above, run the following command from your terminal:

npm run test rangeSum

You’ll notice that we’ve passed all tests. ???? Now let’s test performance.

Testing Performance with JSPerf

Here on JSPerf, we run a performance comparison of the four solutions explored above. The screenshot below reveals the result.

The performance test above reveals that the optimal solution is the For Loop Method. The least optimized solution which is approximately 81% slower is the Recursive Method.

Practical Application

This challenge finds its application in mathematical operations involving number theory and combinatorics. It is also suffices as a coding challenge.

Conclusion

We have now considered four(4) ways to sum up numbers within a specified range. We have also successfully identified the optimal solution to be the For Loop Method. Make sure to explore other ways of solving this challenge. You can always perform a performance comparison using JSPerf as well as share your findings in the comment section.