You don’t need to be a math genius to be a good programmer, but there are a few tricks you can add to your problem solving package to improve the performance of your algorithms and impress in technical interviews. In this tutorial, you’ll learn how to sum a series of consecutive integers from 1 to n using a simple and easy to remember equation. This equation is useful for refactoring a function from O(n) to O(1).

I’m sure 90% of you know arithmetic sequences, but 50% of you think of loop traversal when you see a sum from 1 to n, and even fewer of you think of algorithmic complexity.

1 how do I calculate the sum from 1 to n

How do you add up these figures?

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

Was your first thought a “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
Copy the code

That’s fine, you probably don’t need a pen, paper or calculator to get there. What if the array contains 100, 1,000, or 1,000,000 elements?

2 Code implementation

We could easily write a for loop to automatically add 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);
Copy the code

With a little more elegance, you might use Reduce

const nums = [1.2.3.4.5.6.7.8.9.10];
const x = nums.reduce((a,b) = > a+b);
Copy the code

So that solves the sum problem.

  • So what’s the complexity of the algorithm up here?
  • O(n).

Why is that?

Our function needs to perform one operation on each input, so our algorithm has order O(n) or linear time complexity.

There must be a better way!

Instead of brute force, how about an algorithm to solve this problem?

Look at our array again. Can we sum this in another way?

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

When you sum it, you are likely to start at one end and work towards the other.

Or you might start at the end and work backwards, like this:

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
Copy the code

What happens if we start summing up the front and start summing up the back?

Notice anything?

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

Interesting. What if we started at both ends and worked our way up to the middle?

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

See the pattern?

We have five pairs, and we sum up 11 pairs. The product of these pairs is 55.

But if you don’t know the length of the array, how do you do this calculation?

We will still create the pair, but we will use a variable n as a placeholder for the array length.

1 + n = (n + 1) 2 + n-1 = (n + 1)......Copy the code

Pairs the second element in the array with the penultimate element. The second element is 2 and the penultimate element is the length of the array minus 1, so it’s n minus 1.

What’s the sum of 2 plus n minus 1?

n+1
Copy the code

So let’s move on

3 + n - 2 = n + 1
4 + n - 3 = n + 1
5 + n - 4 = n + 1
Copy the code

At some point we’re going to get to the median of the array. This value is n over 2. The median is 5, which is 10 divided by 2.

What’s n over 2 times n plus 1?

n ( n + 1) / 2
Copy the code

Ok, so we’ve got the rule up here, and now we’re going to plug 10 into this equation up here.

10 times 10 plus 1 over 2 is 55Copy the code

That’s great! We got what we wanted.

But!

This works fine if the length of the array is even. But what if it’s odd? What if our array contains an odd number of elements? As follows:

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

If we plot the high and low value pairs as shown above, we will find a lonely median.

1 plus 9 is 10, 2 plus 8 is 10, 3 plus 7 is 10, 4 plus 6 is 10, 5Copy the code

What’s 5? It’s half of our sum. In other words, the median is half the sum of n plus 1.

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

(n + 1) / 2
Copy the code

Look familiar? If we know the median, what do we do next?

We just multiply that by the length of the array.

n(n + 1) / 2
Copy the code

You can use this array regardless of its length to solve the summation problem. This equation is very useful in helping us improve the efficiency of our algorithms.

Let’s look at the function above. How can we refactor it to improve its algorithmic complexity?

We just need to convert the equation to JavaScript!

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

The algorithm complexity of the above function is reduced to order 1. Our function always performs the same number of operations regardless of the length of the array.

3 How to calculate the sum from 1 to n

In this tutorial, you learned how to sum a series of consecutive integers using a simple and easy to remember equation.

When we’re in interviews, the interviewer will occasionally ask, please write the sum from 1 to 100. From the above, you at least know how to reduce algorithm complexity.

In daily coding, we can reduce algorithm complexity through some rules, set of formulas ~ use it

The original address: [https://dev.to/nielsenjared/improve-your-algorithms-with-this-simple-equation-3g1c]

The last

  • Welcome to pay attention to “front-end plus plus” and share quality articles regularly
  • Reply to add group, invite you into the technical group, long-term technical exchange learning