অ্যারে-এ যোগফল k দিয়ে বিভাজ্য জোড়া গণনা C++-এ

একটি অ্যারে এবং একটি মান k দেওয়া থাকলে, কতটি জোড়ার যোগফল k দিয়ে বিভাজ্য তা গণনা করতে হবে।

উদাহরণ

ইনপুট: arr = [4, 1, 2, 0, 2], k = 2

বৈধ জোড়া: (4,2), (4,0), (2,0), (2,2), (0,2) → মোট 6টি (নোট: আউটপুটে ২ বলা হয়েছে কিন্তু সঠিক ৬টি)

অ্যালগরিদম

সাধারণ (O(n²)): নেস্টেড লুপে সব জোড়া চেক করুন।
দক্ষ (O(n + k)) - মডুলো ফ্রিকোয়েন্সি:
- প্রতিটি উপাদানের arr[i] % k ফ্রিকোয়েন্সি গণনা করুন।
- রিমাইন্ডার ০ এর জোড়া: freq[0] * (freq[0]-1) / 2
- রিমাইন্ডার i এবং k-i এর জোড়া: freq[i] * freq[k-i]
- যদি k জোড় হয়, রিমাইন্ডার k/2 এর জোড়া: freq[k/2] * (freq[k/2]-1) / 2

C++ কোড উদাহরণ (দুই পদ্ধতি)

#include <iostream>
#include <vector>
using namespace std;

// Naive O(n²)
int countPairsNaive(int arr[], int n, int k) {
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if ((arr[i] + arr[j]) % k == 0) count++;
    return count;
}

// Efficient O(n + k)
int countPairsEfficient(int arr[], int n, int k) {
    vector freq(k, 0);
    for (int i = 0; i < n; i++)
        freq[arr[i] % k]++;
    
    long long count = 1LL * freq[0] * (freq[0] - 1) / 2;
    
    for (int i = 1; i <= k/2 && i != k-i; i++)
        count += 1LL * freq[i] * freq[k-i];
    
    if (k % 2 == 0)
        count += 1LL * freq[k/2] * (freq[k/2] - 1) / 2;
    
    return count;
}

int main() {
    int arr[] = {4, 1, 2, 0, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    
    cout << "Naive: " << countPairsNaive(arr, n, k) << endl;
    cout << "Efficient: " << countPairsEfficient(arr, n, k);
    return 0;
}

ইনপুট

[4, 1, 2, 0, 2], k = 2