C++-তে অ্যারে থেকে K দিয়ে বিভাজ্য যোগফল वाले সর্বোচ্চ জোড়া বের করা

টাস্ক হলো একটি অ্যারে arr[] (সাইজ N) থেকে সর্বোচ্চ কতগুলো জোড়া (arr[i] + arr[j]) বের করা যায় যাতে সেগুলো K দিয়ে বিভাজ্য হয়। শর্ত: একই ইন্ডেক্স একাধিক জোড়ায় ব্যবহার করা যাবে না।

ইনপুট

arr[] = {1, 2, 5, 8, 3}, K=2

আউটপুট

ব্যাখ্যা − জোড়া: (0,2) → 1+5=6, (1,3) → 2+8=10। দুটোই ২ দিয়ে বিভাজ্য।

ইনপুট

arr[] = {1, 3, 5, 2, 3, 4}, K=3

আউটপুট

প্রোগ্রামে ব্যবহৃত পদ্ধতি

n ভ্যারিয়েবলে অ্যারের সাইজ রাখুন।
MaxPairs() ফাংশনে আনঅর্ডার্ড ম্যাপ um ব্যবহার করুন। প্রতিটি এলিমেন্টের জন্য um[arr[i]%K]++ করুন।
ম্যাপের সব ভ্যালু ইটারেট করুন।
যদি রিমেইন্ডার ০ হয়, তবে জোড়ার সংখ্যা = um[0]/2।
অন্যান্য রিমেইন্ডার a এর জন্য জোড়া বানাবে min(um[a], um[K-a])।
ব্যবহৃত জোড়া বাদ দিয়ে ম্যাপ আপডেট করুন।

উদাহরণ

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

int MaxPairs(int arr[], int size, int K) {
    unordered_map um;
    for (int i = 0; i < size; i++)
        um[arr[i] % K]++;
    int count = 0;
    for (auto it : um) {
        int first = it.first;
        if (first == 0) {
            count += it.second / 2;
            um[first] = (first % 2 == 0) ? 0 : 1;
        } else {
            int second = K - first;
            if (um[first] < um[second]) {
                count += um[first];
                um[second] -= um[first];
                um[first] = 0;
            } else if (um[first] > um[second]) {
                count += um[second];
                um[first] -= um[second];
                um[second] = 0;
            } else {
                if (first == second) {
                    count += it.second / 2;
                    um[first] = (first % 2 == 0) ? 0 : 1;
                } else {
                    count += um[first];
                    um[first] = 0;
                    um[second] = 0;
                }
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {3, 6, 7, 9, 4, 4, 10};
    int size = sizeof(arr)/sizeof(arr[0]);
    int K = 2;
    cout << "Maximize the number of sum pairs which are divisible by K is: " << MaxPairs(arr, size, K);
    return 0;
}

আউটপুট

Maximize the number of sum pairs which are divisible by K is: 3