Algorithm or mathematics?

What to do on Friday night? Of course, create the account on Leetcode and try something, that's me. I started there with observing weekly contests, and now I want to tell you about one relatively simple problem, that I found curious and suitable for being a showcase of the way I think.

But the first, why do we need mathematical approach in programming? Why can't we just be satisfied with any working solution?

It depends. If development speed is crucial, or tasks don't take so much time to run and they aren't running often - there is not a necessity to optimize this, this may be just waste of time and money. Not always, but most likely.

However, if tasks are heavy or repeatedly running - this is the case. As memory and computational resources are not free at all, it makes sense to review the algorithms and make them as more efficient as it's possible to save time and money. And one of ways to do so - is to apply mathematics.

In this example I'll present my own case where mathematical approach outperformed algorithmic one.

The Problem

Let a is a list like [1, 1, 1, 1, ...] of n elements which are all 1.

After each second the following happens: every element becomes the sum of all the previous elements and itself. Like this:

The question is to found the last element of n-size list after k seconds.

Algorithmic Approach

So, the very intuitive approach is to modify this list k times until getting the final list, from which we can take the last element. This is even simpler than it seems in the beginning:

a = [1] * n  #making a set of ones

for second in range(k):
    for index in range(1, len(a)):
        a[index] += a[index - 1]

# result is a[-1], i.e. the last element of the list        

So, this is just a nested loop. The complexity of this algorithm is O(N^2), i.e. the number of operations is the product of set length n and amount of seconds k. This means complexity will increase significantly with growth of these two coefficients.

Mathematical Approach

However, while observing the table of numbers I made as a little experiment I noticed some symmetry and numbers, that are equal or somehow related to each other. For example 10-20, 35-70, 28-84, 55-220, 165-495.

This was too good to be a coincidence, so I continued to look for patterns. And quite quickly I found one. There was a dynamically changing ratio between elements from the left to the right. I'll bring the example:

1 2 3 4 5 6 series is 1 x 2/1 x 3/2 x 4/3 x 5/4 x 6/5

1 3 6 10 15 21 series is 1 x 3/1 x 4/2 x 5/3 x 6/4 x 7/5

So, I came up with a formula, that describes how the specific number could be calculated.

Afterwards I found another approach to calculation via Combination, i.e. factorials, as it's clearly seen that 3/1 x 4/2 x 5/3 x 6/4 x 7/5 is exactly 3x4x5x6x7 / 1x2x3x4x5 that is 7! / (5! x 2!). This is not so much different in terms of computing, just easier for human perception.

This takes only one loop to describe this formula by code, and makes the complexity of this algorithm O(N), i.e. linear for n.

Performance Comparison

After submission this chart was shown to me:

In this chart we can see exactly the difference between O(N) and O(N^2) performance. The most contestants made a simple algorithmic solution as this was much easier to develop and this was enough to pass through all the test cases. It took about 4.5 seconds in average, while mathematical solution took milliseconds.

It may seem like 4 seconds doesn't make any difference, but if you imagine more calculations with larger numbers, the difference will increase significantly and instead of minutes of calculations, there will be weeks! This was the case before computers appeared, and this is the case now.

Experience

The non-obvious thing for me was using strictly integer division in Python, as common division brings tiny inaccuracies, which affect large numbers.