অ্যারে A এবং পূর্ণসংখ্যা k দেওয়া। কতটি কনটিগুয়াস নন-এমপটি সাবঅ্যারে আছে যেন সাবঅ্যারেটির সম k দিয়ে বিভাজ্য।
উদাহরণ: A=[4,5,0,-2,-3,1], k=5 → ৭টি সাবঅ্যারে।
সমাধানের ধাপসমূহ
- প্রিফিক্স সম মডুলো k ব্যবহার করুন।
- হ্যাশম্যাপ
mরেখে প্রতিটি মডুলো ভ্যালুর ফ্রিকোয়েন্সি ট্র্যাক করুন। m[0] = 1ইনিশিয়ালাইজ করুন।- প্রতিটি উপাদানের জন্য প্রিফিক্স সম আপডেট করুন,
x = (sum % k + k) % k। ans += m[x], তারপরm[x]++।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int subarraysDivByK(vector<int>& a, int k) {
unordered_map<int, int> m;
m[0] = 1;
int sum = 0, ans = 0;
for (int x : a) {
sum += x;
int mod = (sum % k + k) % k;
ans += m[mod];
m[mod]++;
}
return ans;
}
};
int main() {
vector<int> v = {4,5,0,-2,-3,1};
Solution ob;
cout << ob.subarraysDivByK(v, 5);
}
ইনপুট
[4,5,0,-2,-3,1] 5
আউটপুট
7
