Как определить, какое из чисел от 1 до N отсутствует в массиве?

Question

[Вадим]

Как решить данную задачу?

function findN(array){
//На вход подается неупорядоченный массив с целыми числами от 1 до n, 
//каждое число встречается по одному разу, кроме одного, оно отсутствует, 
//необходимо определить какое и вернуть его.
//Желательно, чтобы вычислительная сложность была O(n)
 return -1;
}

Answer 1

[0xD34F]

Отсортировать массив, найти индекс, не равный соответствующему элементу минус один, увеличить индекс на единицу; если такой индекс отсутствует, значит отсутствует последнее число - длина массива плюс один:

function findN([...arr]) {
  const index = arr.sort((a, b) => a - b).findIndex((n, i) => i !== ~-n);
  return -~index || -~arr.length;
}

Желательно, чтобы вычислительная сложность была O(n)

Ненормальный способ - создать массив длиной N, обойти исходный массив, сохраняя в новый информацию о том, какие числа есть, затем в новом массиве выполнить поиск индекса, для которого число в исходном массиве не встретилось:

const findN = arr => -~arr
  .reduce((acc, n) => (acc[~-n] = !1, acc), Array(-~arr.length).fill(!0))
  .findIndex(Boolean);

Нормальный способ - погуглить формулу суммы натуральных чисел от 1 до N, вычесть содержимое массива:

const findN = arr =>
  arr.reduce((acc, n) => acc - n, (arr.length + 2) * (arr.length + 1) / 2);

Ну и в качестве бонуса:

const findN = arr =>
  arr.reduce((acc, n, i) => acc ^ n ^ -~i, -~arr.length);