5191: Codility - Permutation Missing Element
[Creator : ]
Description
Find the missing element in a given permutation.
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.
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:
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.
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)].
Input
First line: N.
Second line: N elements.
Second line: N elements.
Output
One element, the value of the missing element.
Sample 1 Input
4
2 3 1 5
Sample 1 Output
4