การค้นหาตัวเลขที่หายไปในอาร์เรย์ของตัวเลขด้วย JavaScript

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลขที่มีความยาว n โดยอาร์เรย์นี้มีจำนวนเต็มทั้งหมดตั้งแต่ 0 ถึง n (รวม 0 และ n) แต่ขาดตัวเลขเพียงตัวเดียว และอาร์เรย์ไม่ได้เรียงลำดับ ฟังก์ชันต้องค้นหาตัวเลขที่หายไปและคืนค่าในเวลาเชิงเส้น (linear time) และพื้นที่คงที่ (constant space)

แนวคิดการแก้ปัญหา

เนื่องจากอาร์เรย์มีตัวเลขครบทุกตัวตั้งแต่ 0 ถึง n ยกเว้นตัวเดียว เราสามารถคำนวณผลรวมของสมาชิกทั้งหมดในอาร์เรย์ได้ในเวลาเชิงเส้น จากนั้นลบออกจากผลรวมของจำนวนธรรมชาติ n ตัวแรก ซึ่งคำนวณได้ในเวลาคงที่ ผลต่างระหว่างทั้งสองค่านี้คือตัวเลขที่หายไป

ตัวอย่างโค้ด

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));

ผลลัพธ์

9