Solution to Perm-Missing-Elem by codility | Code Says

Solution to Perm-Missing-Elem by codility | Code Says

A zero-indexed 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:

int solution(int A[], int N);

that, given a zero-indexed 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

The main challenge of this question is the XOR operations: X^X=0, and 0^X=X. Logically, the addition and subtraction operations also are able to do this work. But taking the overflow in computer into consideration, they become a very bad choice.

def solution(A):

    length = len(A)

    xor_sum = 0

 

    for index in range(0, length):

        xor_sum = xor_sum ^ A[index] ^ (index + 1)

 

    return xor_sum^(length + 1)

http://codility-lessons.blogspot.com/2014/04/lesson-1-permmissingelem.html
May overflow:

int solution(int A[], int N) 
{
    long sum = ((long)N + 1) * (N + 2) / 2;
    
    int i;

    for (i = 0; i < N; i++){
        sum -= A[i];
    }
    
    return sum;
}

Read full article from Solution to Perm-Missing-Elem by codility | Code Says