Tìm phần tử bị thiếu trong mảng số bằng JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số có độ dài n. Mảng này chứa tất cả các số nguyên từ 0 đến n (kể cả 0 và n), nhưng thiếu đúng một số nguyên bất kỳ, và mảng không được sắp xếp. Nhiệm vụ của hàm là tìm số bị thiếu và trả về nó trong thời gian tuyến tính và không gian hằng số.

Vì mảng chứa tất cả các số từ 0 đến n trừ một số, ta có thể tính tổng tất cả các phần tử của mảng trong thời gian tuyến tính. Sau đó trừ tổng này khỏi tổng n số tự nhiên đầu tiên (có thể tính trong thời gian và không gian hằng số). Hiệu giữa hai tổng chính là số bị thiếu.

Ví dụ

const arr = [3, 7, 8, 10, 11, 0, 2, 6, 1, 4, 5];
const findMissing = (arr = []) => {
  const sum = arr.reduce((acc, val) => acc + val);
  const { length: num } = arr;
  const correctSum = (num * (num + 1)) / 2;
  return correctSum - sum;
};
console.log(findMissing(arr));

Kết quả

9