Đếm tất cả các mảng con có tổng chia hết cho k

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm số mảng con có tổng chia hết cho k.

Đối với điều này, chúng tôi sẽ được cung cấp một mảng và một giá trị k. Nhiệm vụ của chúng ta là tìm số mảng con có tổng của chúng bằng giá trị k đã cho.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//counting subarrays with k sum
int count_subarray(int arr[], int n, int k){
   int mod[k];
   memset(mod, 0, sizeof(mod));
   int cumSum = 0;
   for (int i = 0; i < n; i++) {
      cumSum += arr[i];
      //taking modulus to get positive sum
      mod[((cumSum % k) + k) % k]++;
   }
   int result = 0;
   for (int i = 0; i < k; i++)
      if (mod[i] > 1)
         result += (mod[i] * (mod[i] - 1)) / 2;
   result += mod[0];
   return result;
}
int main(){
   int arr[] = { 4, 5, 0, -2, -3, 1 };
   int k = 5;
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << count_subarray(arr, n, k) << endl;
   int arr1[] = { 4, 5, 0, -12, -23, 1 };
   nt k1 = 5;
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   cout << count_subarray(arr1, n1, k1) << endl;
   return 0;
}

Đầu ra

7
7