##### Short Problem Definition:

Find the missing element in a given permutation.

##### Link

##### Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1)

##### Execution:

Sum all elements that should be in the list and sum all elements that actually are in the list. The sum is 0 based, so +1 is required. The first solution using the + operator can cause int overflow in not-python languages. Therefore the use of a binary XOR is adequate.

##### Solution:

def solution(A): should_be = len(A) # you never see N+1 in the iteration sum_is = 0 for idx in xrange(len(A)): sum_is += A[idx] should_be += idx+1 return should_be - sum_is +1

def solution(A): missing_element = len(A)+1 for idx,value in enumerate(A): missing_element = missing_element ^ value ^ (idx+1) return missing_element

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.