Missing element in Permutation.

Jul 21, 20202 mins read

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:

1function solution(A) {
2}

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)].

Points to be Taken

1.1

1function solution(A) {
2 const b = A.sort()
3 for(let i=0;i<=b.length;i++) {
4 if(b[i+1] !== b[i] + 1) {
5 return b[i] + 1
6 }
7 }
8 return ''
9}

1.2

1function solution(A) {
2 const n = A.length + 1
3 const sumOfN = Math.floor(n * (n + 1) / 2)
4 const sumOfAll = A.reduce((a, b) => a + b, 0)
5 return sumOfN - sumOfAll
6}

Points to be Taken

  1. Array problem expect empty array condition check and single element check.
  2. Arithmetic progression