Codility - Permutation Missing Element

Solution to Codility lesson1-exercise3 Permutation Missing Element problem, link to Codility problem and complete solution at the end of the post.

Definitions:
\mathbf{A} = \{x \in \mathbb{N}\ | 1\leq x \leq N + 1\land |A| = N \}
\{N \in \mathbb{N}\ |\ 0 \leq N \leq 100,000\}

Problem:
Define a function solution with input A, such that solution returns the missing element of the sequence \{1,2,3,...,N-1,N,N+1\}.

  • Expected worst-case time complexity is O(N);
  • Expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified. 

Analysis:

First we must calculate the sum of all elements of the sequence, this can be achieved by using the equation of the sum of elements of an arithmetic progression,

The time for this operation is constant so that gives us O(1).
Now that we have the sum of the sequence, our main strategy will be to visit each element of A, and for each visited element, we will subtract the element value from the sequence sum.

Subtracting all elements of from the sequence sum, will leave us with the missing element. This can be easily seen, since we are summing the inverse of each element of the sequence with itself except for the missing element.
Visiting all the elements of gives us a time complexity of O(N), resulting in a total time complexity of O(N) + O(1), which gives us a final time complexity of O(N).
The space complexity is O(1), since the space required to solve this problem is not dependent on anything.

Complete Solution:

Time Complexity O(N)
Space Complexity O(1)

An alternative solution for big values of N using xor operations by Sheng from Code Says blog can be found here.

Link to GitHub solution here .
Link to Codility problem here .

/*Comment here*/