এই টিউটোরিয়ালে আমরা যোগফল k দিয়ে বিভাজ্য সাব-অ্যারে এর সংখ্যা বের করার প্রোগ্রাম নিয়ে আলোচনা করব।
এই জন্য আমাদের একটি অ্যারে এবং একটি k ভ্যালু দেওয়া থাকবে। আমাদের কাজ হলো যেসব সাব-অ্যারের যোগফল দেওয়া k ভ্যালুর সমান, সেগুলোর সংখ্যা বের করা।
উদাহরণ
#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; }আউটপুট
7 7
