An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

def solution(A)

that, given an array A, returns the value of the missing element.

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5
the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].

#XOR
#ref: https://codesays.com/2014/solution-to-perm-missing-elem-by-codility/

def solution(A):                    #eg A=[2,3,1,5]
    b=0
    for i in range(1,len(A)+1):     #i=1,2,3,4
        b=b^A[i-1]^i                #b=0 ^ (2^1) ^ (3^2) ^ (1^3) ^ (5^4) = 4^5
    return b^(len(A)+1)             #(4^5) ^ 5 = 4
