การนับวิธีการลบ 1 องค์ประกอบเพื่อให้ผลรวม index คู่-คี่เท่ากันใน JavaScript

บทความนี้สาธิตการนับจำนวนวิธีที่ลบ 1 element จากอาร์เรย์ แล้วผลรวมของค่าที่ index คู่เท่ากับผลรวม index คี่

ตัวอย่าง

arr = [2, 6, 4, 2]
// ลบ 6 (index 1): [2,4,2] even sum=4, odd sum=4
// ลบ 2 (index 3): [2,6,4] even sum=6, odd sum=6
// output: 2

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

const arr = [2, 6, 4, 2];

const possibleWays = (arr = []) => {
  const sum = new Array(arr.length);
  let res = 0;
  let oddSum = 0;
  let evenSum = 0;
  for (let i = 0; i < arr.length; ++i) {
    if (i % 2 === 0) sum[i] = (evenSum += arr[i]);
    else sum[i] = (oddSum += arr[i]);
  }
  for (let i = 0; i < arr.length; ++i) {
    if (i % 2 === 0) {
      if (2 * sum[i] - arr[i] + oddSum === 2 * (sum[i - 1] || 0) + evenSum) ++res;
    } else if (2 * sum[i] - arr[i] + evenSum === 2 * (sum[i - 1] || 0) + oddSum) {
      ++res;
    }
  }
  return res;
};

console.log(possibleWays(arr));

ผลลัพธ์

2

คำอธิบาย

คำนวณ prefix sum แยก index คู่/คี่ แล้วสำหรับแต่ละ index i ลองลบ arr[i] และตรวจสอบเงื่อนไข even sum == odd sum

สูตร: หลังลบ index i, even sum ใหม่ = evenSum - (i even ? arr[i] : 0) + (i odd ? arr[i] : 0) ... ใช้ prefix sum คำนวณ O(1) ต่อ index

Time: O(n), Space: O(n)