Tổng số cách xóa phần tử để tổng chỉ số chẵn/lẻ bằng nhau trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số làm đối số đầu tiên và duy nhất.

Hàm sau đó nên thử xóa một phần tử từ mảng, sau khi xóa phần tử đó, tổng các phần tử ở chỉ số lẻ bằng tổng các phần tử ở chỉ số chẵn. Theo cách đó, hàm nên đếm tất cả các cách duy nhất có thể xóa một phần tử tại một thời điểm để đạt được tổ hợp yêu cầu.

Ví dụ:

Nếu mảng đầu vào là:

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

Thì đầu ra nên là 2 vì có 2 phần tử 6 và 2 tại chỉ số 1 và 3 tương ứng làm cho tổ hợp.

Khi xóa 6 khỏi mảng:

[2, 4, 2] so the sum at odd indices = sum at even indices = 4

Khi xóa 2 khỏi mảng:

[2, 6, 4] so the sum at odd indices = sum at even indices = 6

Ví dụ

Dưới đây là mã nguồn:

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

Kết quả

Đầu ra trên console:

2

Giải thích: Tính prefix sum riêng cho chỉ số chẵn/lẻ. Khi xóa phần tử tại i, các phần tử sau i đổi parity chỉ số. Công thức kiểm tra cân bằng sau xóa. O(n) time, O(n) space.