Perm Missing Element Find the missing element in a given permutation.
Problem
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.
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)].
Example
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.
Hint
Concept 1: Arithmetic Progression
General case of Arithmetic Progression.
An arithmetic progression (AP) is a sequence of numbers in which the difference of any two successive members is a constant. This constant difference is often denoted by "d." The general form of an arithmetic progression is:
a, a+d, a+2d, a+3d, …
Here:
a is the first term (initial term) of the sequence.
d is the common difference between consecutive terms.
For example, consider the arithmetic progression with a first term (a) of 3 and a common difference (d) of 2:
3, 5, 7, 9, 11,…
Sum of an A.P. is: [2a+(n−1)d] * n / 2
Concept 2: Triangular Numbers
Which is a specific case of Arithmetic Progression.
Triangular numbers are a sequence of numbers that represent the number of objects that can be arranged in the shape of an equilateral triangle. The n-th triangular number is the sum of the first n natural numbers. The formula for the n-th triangular number, often denoted as Tn, is given by:
Tn=1+2+3+…+n = n⋅(n+1) / 2
The sequence of triangular numbers begins with:
1, 3, 6, 10, 15, 21,…
Code
We will use the idea of N’th Triangular number to find our missing number using the following steps:
1. We find the ideal sum if the missing number were also there.
This is given by the formula for the sum of an A.P. or formula for N’th Triangular number.
2. We find the sum of input we have.
3. Missing number = result_from_step_1 - result_from_step_2
def solution(A):
# Implement your solution here
sum_of_series = (len(A) + 1) * (len(A) + 2) / 2
sum_of_input = sum(A)
missing_element = int(sum_of_series - sum_of_input)
return missing_element
Detected Time Complexity
- O(N) or O(N * log(N))
Test Cases
Correctness tests
empty_and_single
empty list and single element
missing_first_or_last
the first or the last element is missing
single
single element
double
two elements
simple
simple test
Performance tests
medium1
medium test, length = ~10,000
medium2
medium test, length = ~10,000
large_range
range sequence, length = ~100,000
large1
large test, length = ~100,000
large2
large test, length = ~100,000