Tổng chia hết cho n trong JavaScript

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào mảng số arr làm đối số 1, và số num làm đối số 2. Hàm trả về số lượng mảng con (liên tiếp, không rỗng) có tổng chia hết cho num.

Ví dụ, nếu đầu vào là:

const arr = [4, 5, 0, -2, -3, 1]; 
const num = 5;

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

const output = 7;

Giải thích đầu ra

Có 7 mảng con tổng chia hết cho 5:

[4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3]

Ví dụ minh họa

Mã thực hiện (tiền tố modulo + tổ hợp):

const arr = [4, 5, 0, -2, -3, 1]; 
const num = 5; 
const divisibleSum = (arr = [], num = 1) => { 
  const map = {}; 
  let sum = 0; 
  for (let i = 0; i < arr.length; i++) { 
    sum += arr[i]; 
    const key = ((sum % num) + num) % num; 
    map[key] = map[key] + 1 || 1; 
  }; 
  let s = 0; 
  for (let i = 0; i < num; i++) { 
    if (map[i] > 1) { 
      s += (map[i] * (map[i] - 1)) / 2; 
    } 
  } 
  return s + (map[0] || 0); 
}; 
console.log(divisibleSum(arr, num));

Đầu ra

Kết quả trong console sẽ là:

7