การลบ subarray สั้นที่สุดเพื่อให้ผลรวมอาร์เรย์หารตัวเลขลงตัวใน JavaScript

บทความนี้สาธิตการหาความยาว subarray สั้นที่สุดที่ต้องลบ เพื่อให้ผลรวมอาร์เรย์ที่เหลือหาร num ลงตัว

ตัวอย่าง

arr = [3, 8, 2, 6], num = 9
total = 19, 19 % 9 = 1 -> ต้องลบ subarray ที่ sum % 9 = 1
subarray [8,2] sum=10, 10%9=1 -> ลบได้ output: 2

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

const arr = [3, 8, 2, 6];
const num = 9;

const minimumDeletion = (arr = [], num) => {
  const diff = arr.reduce((a, b) => a + b) % num;
  let res = diff == 0 ? 0 : arr.length;
  for (let i = 0, sum = 0, map = {0: -1}; i < arr.length; i++) {
    sum += arr[i];
    const target = (sum % num - diff + num) % num;
    if (map[target] != undefined) {
      res = Math.min(res, i - map[target]);
    }
    map[sum % num] = i;
  }
  return res == arr.length ? -1 : res;
};

console.log(minimumDeletion(arr, num));

ผลลัพธ์

2

คำอธิบาย

ใช้ prefix sum modulo: หา prefix sum ที่ (current - target) % num = diff โดยเก็บ first occurrence ของแต่ละ modulo ใน map

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