Thinking Process of an algorithm of find the missing element in a given permutation from Codility

Question

I found this perfect answer for the Codility's PermMissingElem Question.

function solution($A) {
    $N   = count($A);
    $sum = ($N + 2) * ($N + 1) / 2;
    for($i = 0; $i < $N; $i++){
        $sum -= $A[$i];
    }
    return intval($sum);
}

However I found its puzzled for me regarding the $sum's function. What kind of function is this? It's amazingly correctly, yet, how come someone could make up such function? Is there anyone can somehow reverse engineer the thinking process? I really want to know the process how it came about.

Thank You !

http://stackoverflow.com/questions/27959397/duplicate-element-in-array/27959534#27959534 apart from this question which is similar I am sure this is a duplicate — advocateofnone, Jan 27 '15 at 16:55

score 1 · Accepted Answer · answered Jan 27 '15 at 20:34

1

The sum of integers from 1 to N can be calculated by this formula:

N(N+1)/2

Basically, you take the first number and the last number and add them together, and then the second number and the second to last number..etc.

For example:

The sum of 1 to 100:

(1+100) + (2+99) + (3+98) + (4+97) ...
= (100/2)(101)
= 50 x 101

Here's a good explanation:

http://www.wikihow.com/Sum-the-Integers-from-1-to-N

answered Jan 27 '15 at 20:34

Vic

8,261
6
42
55

I know its amateur... But its just wow, still, so amazing!.... Learned it couple years back, totally forgot about it lol Thanks man :) – ey dee ey em Feb 02 '15 at 20:49

Thinking Process of an algorithm of find the missing element in a given permutation from Codility

1 Answers1