আমাদেরকে শুধুমাত্র পূর্ণসংখ্যা সম্বলিত একটি অ্যারে arr[] দেওয়া হয়েছে। লক্ষ্য হল arr[] এর পরবর্তী সংখ্যার সংখ্যা খুঁজে বের করা যাতে তাদের সর্বাধিক সংখ্যক স্বতন্ত্র উপাদান থাকে। যদি অ্যারেটি [ 4,1,2,3,4 ] হয় তাহলে দুটি পরবর্তি হবে [ 4,1,2,3 ] এবং [ 1,2,3,4 ]৷
আসুন উদাহরণ দিয়ে বুঝতে পারি
ইনপুট − arr[]={ 1,3,5,4,2,3,1 }
আউটপুট − সর্বাধিক স্বতন্ত্র উপাদান সম্বলিত পরবর্তী সংখ্যার সংখ্যা হল − 4
ব্যাখ্যা − সর্বাধিক স্বতন্ত্র উপাদানগুলি হল 1,2,3,4 এবং 5৷ গণনা হল 5৷ পরবর্তীগুলি হবে −
[ 1,3,5,4,2 ], [ 3,5,4,2,1], [ 5,4,2,3,1 ], [ 1,5,4,2,3]।
ইনপুট − arr[]={ 5,4,2,1,3 }
আউটপুট − সর্বাধিক স্বতন্ত্র উপাদান সম্বলিত পরবর্তী সংখ্যার সংখ্যা হল − 1
ব্যাখ্যা - সমস্ত উপাদান স্বতন্ত্র। পরবর্তী সংখ্যা 1 হবে।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা এই সত্যের উপর ভিত্তি করে পরবর্তী অনুক্রমগুলি খুঁজে পাব যে যদি সমস্ত উপাদান আলাদা হয় তবে অনুগামী সংখ্যা হল 1 যা নিজেই অ্যারে। যদি পুনরাবৃত্ত উপাদান থাকে তবে প্রতিটি পুনরাবৃত্ত উপাদান একটি নতুন পরবর্তী অংশের অংশ হবে। তাই আমরা স্বতন্ত্র উপাদানগুলির ফ্রিকোয়েন্সিগুলির একটি unordered_map তৈরি করব। তারপর প্রতিটি কম্পাঙ্কের জন্য সেই ফ্রিকোয়েন্সি গুণ করে গণনা করুন। শেষে গণনায় ফ্রিকোয়েন্সির মোট সংখ্যা রয়েছে।
-
ইনপুট হিসাবে একটি পূর্ণসংখ্যা অ্যারে arr[] নিন।
-
ফাংশন Max_distinct_subseq(int arr[], int size) অ্যারে এবং এর আকার নেয় এবং সর্বাধিক স্বতন্ত্র উপাদান সহ পরবর্তী সংখ্যার গণনা প্রদান করে।
-
প্রারম্ভিক গণনাকে 1 হিসাবে ধরুন যেন সমস্ত উপাদান স্বতন্ত্র হয় তাহলে অ্যারে নিজেই সর্বাধিক স্বতন্ত্র উপাদানগুলির সাথে পরবর্তী।
-
unordered_map
-
হ্যাশ[arr[i]]]++ ব্যবহার করে লুপ এবং আপডেট ফ্রিকোয়েন্সি প্রতিটি উপাদানের জন্য অ্যারে ব্যবহার করুন।
-
এখন একটি ফর লুপ ব্যবহার করে হ্যাশ অতিক্রম করুন। প্রতিটি কম্পাঙ্কের জন্য it->সেকেন্ড( it=iterator) পূর্ববর্তী গণনায় গুণ করুন। যেহেতু একই সময়ের x উপাদানগুলো হবে x ভিন্ন অনুসারীর অংশ।
-
শেষে গণনায় ফ্রিকোয়েন্সির মোট সংখ্যা রয়েছে।
-
ফলাফল হিসাবে রিটার্ন গণনা।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int Max_distinct_subseq(int arr[], int size){
int count = 1;
unordered_map<int, int> hash;
for (int i = 0; i < size; i++){
hash[arr[i]]++;
}
for (auto it = hash.begin(); it != hash.end(); it++){
count = count * (it->second);
}
return count;
}
int main(){
int arr[] = { 3, 7, 3, 3, 1, 5, 6, 9 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subsequences having maximum distinct elements are: "<<Max_distinct_subseq(arr, size);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of subsequences having maximum distinct elements are: 3
