Xóa mảng con nhỏ nhất để tổng mảng chia hết trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số nguyên dương làm đối số đầu tiên và một số nguyên dương làm đối số thứ hai.

Hàm nên tìm ra và trả về độ dài của mảng con nhỏ nhất mà chúng ta nên xóa từ mảng gốc để làm cho tổng của nó chia hết cho số được chỉ định bởi đối số thứ hai.

Ví dụ:

Nếu đầu vào là:

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

Thì đầu ra nên là:

const output = 2

Vì mảng con cần xóa là [8, 2]

Ví dụ

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

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

Kết quả

Đầu ra trên console:

2

Giải thích: Tổng mảng = 19, 19%9=1 (diff). Cần xóa subarray có sum%9=1. Dùng prefix sum modulo + hashmap lưu earliest index của mỗi modulo. Tìm subarray ngắn nhất có modulo = diff. O(n) time.