loading...
Cover image for Improve Your Algorithms with this Simple Equation

Improve Your Algorithms with this Simple Equation

nielsenjared profile image Jared Nielsen Originally published at jarednielsen.com ・5 min read

You don’t need to be a math whiz to be a good programmer, but there are a handful of tricks you will want to add to your problem solving bag to improve the performance of your algorithms and make an impression in technical interviews. In this tutorial, you will learn how to sum a series of consecutive integers from 1 to n with a simple and easy to remember equation. This equation is useful for refactoring a function from O(n) to O(1) and calculating the complexity of nested iterations with offsets.

This article originally published on jarednielsen.com

How to Sum Integers 1 to n

How would you add these numbers?

[1,2,3,4,5,6,7,8,9,10]

Was your first thought to take the ‘brute force’ approach?

1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15
15 + 6 = 21
21 + 7 = 28
28 + 8 = 36 
36 + 9 = 45
45 + 10 = 55

Nothing wrong with that and you probably didn’t need pen and paper or a calculator to get there.

What if the array contained 100 or 1,000 or 1,000,000 elements?

Brute force would be brutal.

Programming is Problem Solving

What is programming?

Programming is problem solving.

What problems do we solve?

There are two primary categories of problems we solve as programmers:

  • Automation
  • Algorithms

We could easily write a for loop to automate the addition of our series:

const nums = [1,2,3,4,5,6,7,8,9,10];

const sumHarder = arr => {
   let sum = 0;
   for (let i = 0; i < arr.length; i++) {
       sum += arr[i];
   }
   return sum;
}

const result = sumHarder(nums);

That solves the problem of needing to manually sum the numbers.

Will it scale?

What’s the Big O?

O(n).

Why?

Our function needs to perform one operation for every input, so the order of our algorithm is O(n) or linear time complexity.

There must be a better way!

Rather than automate the brute force approach, how can we solve this problem algorithmically?

Take another look at our array. Is there a different approach we could take to find the sum?

[1,2,3,4,5,6,7,8,9,10]

When you added the series, you most likely started at one end and worked towards the other.

Or maybe you started at the end and worked backwards, like so:

10 + 9 = 19
19 + 8 = 27
27 + 7 = 34
34 + 6 = 40
40 + 5 = 45
45 + 4 = 49
49 + 3 = 52
53 + 2 = 54
54 + 1 = 55

What if we put our forward and back approaches side-by-side?

Sum Up 🌄 Sum Down 🌆
1 + 2 = 3 10 + 9 = 19
3 + 3 = 6 19 + 8 = 27
6 + 4 = 10 27 + 7 = 34
10 + 5 = 15 34 + 6 = 40
15 + 6 = 21 40 + 5 = 45
21 + 7 = 28 45 + 4 = 49
28 + 8 = 36 49 + 3 = 52
36 + 9 = 45 53 + 2 = 54
45 + 10 = 55 54 + 1 = 55

Notice anything?

If we sum the sums in each row of our table, we get multiples of 11.

Sum Up 🌄 Sum Down 🌆 Sum All Around 🌞
1 + 2 = 3 10 + 9 = 19 3 + 19 = 22
3 + 3 = 6 19 + 8 = 27 6 + 27 = 33
6 + 4 = 10 27 + 7 = 34 10 + 34 = 44
10 + 5 = 15 34 + 6 = 40 15 + 40 = 55
15 + 6 = 21 40 + 5 = 45 21 + 45 = 66
21 + 7 = 28 45 + 4 = 49 28 + 49 = 77
28 + 8 = 36 49 + 3 = 52 36 + 52 = 88
36 + 9 = 45 53 + 2 = 54 45 + 54 = 99
45 + 10 = 55 54 + 1 = 55 55 + 55 = 110

Interesting… 🤔

What if we started at both ends, and worked our way to the middle?

1 + 10 = 11
2 + 9 = 11
3 + 8 = 11
4 + 7 = 11
5 + 6 = 11

See a pattern?

We have five pairs each summing to 11. The product of those pairs is, you guessed it, 55.

🤯

How do you make this calculation if you don’t know the length of your array?

We will still make our pairs, but we’ll use a variable, n, as a placeholder for the length of our array.

1 + n    = (n+ 1)
2 + n -1 = (n + 1)

Wait! What? Why n -1?

We want to pair the second element in our array with the second to last element. The second element is 2 and the second to last element is the length of our array minus 1, so n-1. What is the sum of 2 + n -1 ?

n + 1

I think you see where this is going.

3 + n - 2 = n + 1
4 + n - 3 = n + 1
5 + n -4  = n + 1

At some point we will reach the median of our array. That value will be n / 2. Here, our median is 5, which is the quotient of 10 divided by 2.

What is n / 2 multiplied by n + 1?

n ( n + 1) / 2

When we manually mapped out our pairs earlier, how did we perform our calculation? We multiplied 11, the sum of our high and low values, by 5, which is 10 divided by 2. Let’s plug 10 into our equation.

10 ( 10 + 1) / 2 = 55

Following the order of operations:

10 + 1 = 11
11 * 10 = 110
110 / 2 = 55

Mathemagical! ✨

But!

A quick eye will notice that this works well if our array is even in length. What if it’s not? What if our array contains an odd number of elements?

[1,2,3,4,5,6,7,8,9]

If we map out our high / low value pairs, we find ourselves with a lonely median:

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

Notice that the values all sum to an even number, unlike with our even length array, in which the low/high pairs summed to an odd number.

So what is 5? It’s half the sum of our pairs. In other words, our median is half the sum of n + 1.

We can write this as an equation to identify the median:

(n + 1) / 2

Look familiar? What’s missing?

If we know the median, what do we need to do next?

We simply need to multiply this value by the length of our array.

n(n + 1) / 2

Regardless of the array length, this equation is incredibly useful in helping us make our algorithms more efficient.

Let’s take another look at our function above. How can we refactor this to improve its Big O?

const nums = [1,2,3,4,5,6,7,8,9,10];

const sumHarder = arr => {
   let sum = 0;
   for (let i = 0; i < arr.length; i++) {
       sum += arr[i];
   }
   return sum;
}

We simply translate our equation into JavaScript!

const sumSmarter = arr => arr.length * (arr.length + 1)/2;

What's the order of our new function?

O(1).

Regardless of the length of the array, our function will always perform the same number of operations.

How to Sum Integers 1 to n

You don’t need to be a math whiz to be a good programmer, but there are a handful of equations you will want to add to your problem solving toolbox. In this tutorial, you learned how to sum a series of consecutive integers with a simple and easy to remember equation. It’s like a party trick for technical interviews.


Want to level up your problem solving skills? I write a weekly newsletter about programming, problem solving and lifelong learning. Sign up for The Solution


Discussion

markdown guide
 

I also like the more visual geometric proof of this formula. Say you want the sum of 1-4, you can make this shape:

*
**
***
****

The area of this triangle is then equivalent to our original problem, the sum of the first 4 natural numbers. But, it's hard to find the area of this "triangle", but easy if you make a rectangle (#s are a second, rotated copy of the triangle)

*####
**###
***##
****#

This is a 5x4 rectangle, so its area is 20. The rectangle is made of two of the triangles we want to know the area of, so the sum is 20/2 = 10.

If you generalize this to the first n natural numbers, you do indeed get the formula n (n + 1) / 2

 

This is great! I sketched something similar in this post on quadratic complexity jarednielsen.com/big-o-quadratic-t..., but I like yours better. Do you mind if I use it? With credit, of course.

 
 

There is no excuse to forget the formula now!
I mean, you don't even need to list cases.

 

But calculating the array length has a cost of O(N). At the end there is no improvement un complexity

 
 

Array length isn't "calculated" it's a property of the Array, so to get the Array.length it is just O(1).

 

This is really interesting. However the only thing I find IS that it depends on the implementation.
Could you please send a source? I'm really interested on how this property gets calculated

maybe joel is talking about javascript. Hes right its a property of an array. Thats how V8 implements it (sorry I cant find the link but Its in v8.dev). In other programming languages its still O(1) or constant time because it will do an arithmetic operation, example before c++14 (not sure) we do it in class was like totalNumberOfbytesInArray / numberOfBytesInInt. or maybe im wrong because it was 2008. lools

When an item is added to or removed from the array, the length property is updated. You can check this by running this code:

const array = [1, 2, 3];
array.length = 100;

console.log(array.length) //=> 100

length NEEDS to be a property, otherwise code like this would become exponential:

for (let i = 0; i < input.length; i++) { }

I think this Tweet is relevant to the discussion:

 

I suggest reading a good book about Discrete Mathematics. Currently I'm reading this one which is very helpful.

Revisiting those topics help you understand how useful they are in computers and computations.

 

Anecdotally, this algorithm is said to be applied (and possibly developed) by young Gauss at his age of 10. :-)

 
 

I prefer the simpler proof:

S = 1 + 2 + 3 + . ... + n

S = n + (n-1) + (n-2) + ... + 1


2S = (n+1) + (n+1) + (n+1) + ... + (n+1) = n (n+1)

=> S = n (n+1)/2

Interestingly the formula is O(1) if you consider the addition/multiplication/division to be ATOMIC. But in reality such operations take O(N) time with regard to the LENGTH OF THE INPUT |N| which in this case is Log N.

So the algorithm really takes O(N) time with respect to INPUT SIZE rather than O(1) (but O(logN) time with respect to N's value if you consider the realities of the bitwise math operations). This becomes evident if you start using 1000 bit numbers for example.

This common confusion may lead people to believe that there's a polynomial time solution to the "efficient" fibonacci number:

 def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a+b
    return a

(source: stackoverflow.com/questions/181722...)

But actually since the INPUT SIZE here is Log N, the algorithm is said to be "pseudo-polynomial" because its polynomial (O(N)) with regard to the value of N, but its actually EXPONENTIAL with regard to the input size Log N.

Again this becomes evident when you realize just how many bits you're going to need to represent that result.

Note: this probably has no bearing on your real world algorithm as long as you live within the confines of 32 bit of 64 bit numbers. :)

More on this confusing topic here: cs.stackexchange.com/questions/164...

 

npm i sum-numbers-in-array

 

Couldn't find that one, but this is close npmjs.com/package/array-sum

 

yeahh it was a joke hehe, thanks for the article btw. I liked it!

 

Nice post, Jared.

Too complicated for me. 🤯

 

How about sum of any arithmetic series ?
varsitytutors.com/hotmath/hotmath_...

To find the sum of the first n terms of an arithmetic sequence use the formula,
Sn=n(a1+a2)/2 ,where n is the number of terms, a1 is the first term and an is the last term.


Find the sum of the first 40 terms of the arithmetic sequence : 2,5,8,11,14,⋯
First find the 40 th term: a40=a1+(n−1)d =2+39(3)=119
Then find the sum . 40(2+119) / 2 = 2420

 

Thanks for sharing this. I have been looking to improve my knowledge of algorithms.

Just subscribed to your newsletter.

 
 

Hey dude, great article!

I'm just missing one thing

do i have to assume this list is always sorted?

 

This is just a formula for adding up the numbers 1 to n (the order you add numbers doesn't matter).

If you have a collection of numbers that you don't know the structure to (ie, it's not something as simple as an arithmetic sequence), there's no trick to adding them up faster that's faster than doing it one by one.

 
 

Absolutely wonderful article for non maths major.