দেওয়া টাস্ক হল arr[i] + arr[j] জোড়ার সর্বাধিক সংখ্যা গণনা করা যা K দ্বারা বিভাজ্য যেখানে arr[] হল N পূর্ণসংখ্যা সম্বলিত একটি অ্যারে।
শর্ত দেওয়া হয়েছে যে একটি নির্দিষ্ট সূচক নম্বর একাধিক জোড়ায় ব্যবহার করা যাবে না।
ইনপুট
arr[]={1, 2 ,5 ,8 ,3 }, K=2 আউটপুট
2
ব্যাখ্যা − কাঙ্খিত জোড়া হল:(0,2), (1,3) হিসাবে 1+5=6 এবং 2+8=10। 6 এবং 10 উভয়ই 2 দ্বারা বিভাজ্য।
বিকল্প উত্তর জোড়া হতে পারে:(0,4), (1,3) বা (2,4), (1,3) কিন্তু উত্তর একই থাকে, অর্থাৎ 2।
ইনপুট
arr[]={1 ,3 ,5 ,2 ,3 ,4 }, K=3 আউটপুট
3
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
int-এর ভেরিয়েবল n-এ অ্যারের আকার সংরক্ষণ করে
-
ফাংশনে MaxPairs() বিন্যাসহীন মানচিত্র ব্যবহার করে এবং অ্যারের প্রতিটি উপাদানের জন্য একটি করে um[arr[i]%K] হিসাবে মান বাড়ায়।
-
পুনরাবৃত্তি করুন এবং প্রতিটি সম্ভাব্য উম মান পান।
-
যদি um এর মান শূন্য হয় তাহলে জোড়ার সংখ্যা হবে um[0]/2।
-
তারপর ন্যূনতম (um[a], um[Ka]) ব্যবহার করে প্রতিটি উম মান 'a' থেকে জোড়া তৈরি করা যেতে পারে
-
উম মান থেকে বিয়োগ করুন, ব্যবহৃত জোড়ার সংখ্যা।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int MaxPairs(int arr[], int size, int K){
unordered_map<int, int> um;
for (int i = 0; i < size; i++){
um[arr[i] % K]++;
}
int count = 0;
/*Iteration for all the number that are less than the hash value*/
for (auto it : um){
// If the number is 0
if (it.first == 0){
//Taking half since same number
count += it.second / 2;
if (it.first % 2 == 0){
um[it.first] = 0;
}
else{
um[it.first] = 1;
}
}
else{
int first = it.first;
int second = K - it.first;
// Check for minimal occurrence
if (um[first] < um[second]){
//Taking the minimal
count += um[first];
//Subtracting the used pairs
um[second] -= um[first];
um[first] = 0;
}
else if (um[first] > um[second]){
// Taking the minimal
count += um[second];
//Subtracting the used pairs
um[first] -= um[second];
um[second] = 0;
}
else{
//Checking if the numbers are same
if (first == second){
//If same then number of pairs will be half
count += it.second / 2;
//Checking for remaining
if (it.first % 2 == 0)
um[it.first] = 0;
else
um[it.first] = 1;
}
else{
//Storing the number of pairs
count += um[first];
um[first] = 0;
um[second] = 0;
}
}
}
}
return count;
}
//Main function
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
