การคำนวณ Weighted Sum ของ Nested Array ใน JavaScript

ปัญหา

คำนวณ weighted sum ของ nested array: element * depth (depth เริ่มที่ 1)

ตัวอย่าง

arr = [4, 7, [6, 1, [5, 2]]]
sum = 4*1 + 7*1 + 6*2 + 1*2 + 5*3 + 2*3 = 46

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

const arr = [4, 7, [6, 1, [5, 2]]];

const findWeightedSum = (arr = [], level = 1, res = 0) => {
  for (let i = 0; i < arr.length; i++) {
    if (typeof arr[i] === 'number') {
      res += (level * arr[i]);
    } else if (Array.isArray(arr[i])) {
      return findWeightedSum(arr[i], level + 1, res);
    }
  }
  return res;
};

console.log(findWeightedSum(arr));

ผลลัพธ์

46

คำอธิบายและแก้ไข

บั๊กในโค้ดต้นฉบับ: recursive call `return findWeightedSum(...)` จะ return ทันที ไม่สะสมผลลัพธ์จาก sibling arrays

โค้ดที่แก้ไข:

const findWeightedSum = (arr = [], level = 1) => {
  let res = 0;
  for (let i = 0; i < arr.length; i++) {
    if (typeof arr[i] === 'number') {
      res += level * arr[i];
    } else if (Array.isArray(arr[i])) {
      res += findWeightedSum(arr[i], level + 1);
    }
  }
  return res;
};

Time: O(n) n = total elements, Space: O(d) d = max depth