Perm Missing Elem

11 Apr, 2021

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:

function solution(A);

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

My Solution

function solution(A) {
	if (!A.length || A.length === 1) return;
	let max = Math.max(...A);
	let min = Math.min(...A);

	for (let i = min; i < max; i++) {
		if (!A.includes(i)) return i;
	}
}

function solution(A) {
	if (!A.length || A.length === 1) return;

	A.sort((b, a) => b - a);

	for (let i = 0; i < A.length; i++) {
		if (A[i] + 1 !== A[i + 1]) return A[i] + 1;
	}
}

Best Practice

function solution(A) {
	// using serial number sum formula
	const expectedSum = ((A.length + 1) * (A.length + 2)) / 2;
	const realSum = A.reduce((sum, el) => sum + el, 0);
	return expectedSum - realSum;
}