นับซับอาร์เรย์ที่ผลรวมหารด้วย k ลงตัว

ในบทช่วยสอนนี้ เราจะอภิบายโปรแกรมเพื่อหาจำนวนซับอาร์เรย์ที่ผลรวมหารด้วย k ลงตัว

สำหรับเรื่องนี้ เราจะได้รับอาร์เรย์และค่า k งานของเราคือหาจำนวนซับอาร์เรย์ที่มีผลรวมเท่ากับค่า k ที่กำหนด

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

// counting subarrays with sum divisible by k
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 };
    int k1 = 5;
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << count_subarray(arr1, n1, k1) << endl;
    return 0;
}

เอาต์พุต

7
7