Jay Taylor's notes

back to listing index

Which Appears Twice | Interview Cake

[web search]
Original source (www.interviewcake.com)
Tags: math algorithms series www.interviewcake.com
Clipped on: 2016-07-16

First, we sum all numbers 1...n1...n1...n. We can do this using the equation:

n2+n2\frac{n^2 + n}{2}2n2+n

because the numbers in 1...n1...n1...n are a triangular series

A triangular series is a series of numbers where each number could be the row of an equilateral triangle.

So 1, 2, 3, 4, 5 is a triangular series, because you could stack the numbers like this:

Their sum is 15, which makes 15 a triangular number.

A triangular series always starts with 1 and increases by 1 with each number.

Since the only thing that changes in triangular series is the value of the highest number, it’s helpful to give that a name. Let’s call it n.

  # n is 8
1, 2, 3, 4, 5, 6, 7, 8

Triangular series are nice because no matter how large n is, it’s always easy to find the total sum of all the numbers.

Take the example above. Notice that if we add the first and last numbers together, and then add the second and second-to-last numbers together, they have the same sum! This happens with every pair of numbers until we reach the middle. If we add up all the pairs of numbers, we get:

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

This is true for every triangular series:

  1. Pairs of numbers on each side will always add up to the same value
  2. That value will always be 1 more than the series’ n

This gives us a pattern. Each pair's sum is n+1n+1n+1, and there are n2\frac{n}{2}2n pairs. So our total sum is: (n+1)n2(n + 1) * \frac{n}{2}(n+1)2n

Or:

n2+n2\frac{n^2 + n}{2}2n2+n