প্রদত্ত কাজটি হল একটি প্রদত্ত লিঙ্কযুক্ত তালিকায় ন্যূনতম ফ্রিকোয়েন্সি উপাদানগুলি গণনা করা যাতে ডুপ্লিকেট উপাদান রয়েছে৷
একটি লিঙ্ক করা তালিকা হল একটি ডেটা স্ট্রাকচার যেখানে ডেটা সিরিয়াল ক্রমে সংরক্ষণ করা হয়, যেমন একটি তালিকা প্রতিটি উপাদান পরবর্তী উপাদানের সাথে লিঙ্ক করা হয়।
একটি লিঙ্ক তালিকায় একটি উপাদানের ফ্রিকোয়েন্সি লিঙ্ক করা তালিকায় একটি উপাদান ঘটছে তার সংখ্যা বোঝায়। সমস্যা অনুসারে আমাদের একটি লিঙ্ক করা তালিকায় সর্বনিম্ন ফ্রিকোয়েন্সি গণনা করতে হবে।
ধরা যাক আমাদের একটি লিঙ্ক করা তালিকা আছে, 1, 1, 3, 1, 3, 4, 6; যেখানে ন্যূনতম ফ্রিকোয়েন্সি একটি তাই আমাদের উপাদানগুলিকে গণনা করতে হবে, যাদের ন্যূনতম ফ্রিকোয়েন্সি রয়েছে। সর্বনিম্ন ফ্রিকোয়েন্সি সহ শুধুমাত্র দুটি উপাদান 4 এবং 6 আছে তাই গণনা 2।
ইনপুট −
linked list 1->1->2->2->2->3->3
আউটপুট −
count is 2
ব্যাখ্যা −
উপরের উদাহরণে ন্যূনতম ফ্রিকোয়েন্সি হল 2 এবং ন্যূনতম ফ্রিকোয়েন্সি সহ দুটি উপাদান রয়েছে যেমন 1 এবং 3, তাই গণনা হল 2৷
ইনপুট −
linked list = 1->2->3->2->4->2->5
আউটপুট −
count is 4
ব্যাখ্যা −
উপরের উদাহরণে সর্বনিম্ন ফ্রিকোয়েন্সি হল 1 এবং সর্বনিম্ন ফ্রিকোয়েন্সি সহ 4টি উপাদান রয়েছে যেমন 1, 3, 4, এবং 5, তাই গণনা হল 4৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
একটি লিঙ্ক করা তালিকা সংজ্ঞায়িত করুন এবং লিঙ্ক করা তালিকার উপাদানগুলিকে পুশ করুন৷
৷ -
ন্যূনতম কম্পাঙ্ক সহ উপাদানগুলির গণনা খুঁজে পেতে সর্বনিম্ন ফাংশনে, সংখ্যার ফ্রিকোয়েন্সি সংরক্ষণ করতে একটি মানচিত্র "mymap" ঘোষণা করুন৷
-
তালিকাটি অতিক্রম করুন এবং mymap-এ উপাদানগুলির ফ্রিকোয়েন্সি (ঘটনা) সংরক্ষণ করুন৷
৷ -
আমরা ফ্রিকোয়েন্সিগুলি খুঁজে পাওয়ার পরে এবং ফ্রিকোয়েন্সিগুলি mymap-এ সংরক্ষণ করার পরে, তারপর সর্বনিম্ন ফ্রিকোয়েন্সি খুঁজুন৷
-
মাইম্যাপে কতবার ঘটেছে তা গণনা করুন।
-
গণনা ফেরত দিন।
উদাহরণ
#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;
struct Node {
int key;
struct Node* next;
};
// to push the values in the stack
void push(struct Node** head_ref, int new_key){
struct Node* new_node = new Node;
new_node->key = new_key;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Function to count minimum frequency elements
// in the linked list
int minimum(struct Node* head){
// Store frequencies of all nodes.
unordered_map<int, int> mymap;
struct Node* current = head;
while (current != NULL){
int value = current->key;
mymap[value]++;
current = current->next;
}
// Find min frequency
current = head;
int min = INT_MAX, count = 0;
for (auto it = mymap.begin(); it != mymap.end(); it++){
if (it->second <= min){
min = it->second;
}
}
// Find count of min frequency elements
for (auto it = mymap.begin(); it != mymap.end(); it++){
if (it->second == min){
count += (it->second);
}
}
return count;
}
int main(){
/* Starting with an empty list */
struct Node* head = NULL;
int x = 21;
push(&head, 30);
push(&head, 50);
push(&head, 61);
push(&head, 40);
push(&head, 30);
cout <<"count is: "<<minimum(head) << endl;
return 0;
} আউটপুট
আমরা উপরের কোডটি চালালে আমরা নিম্নলিখিত আউটপুট পাব −
count is: 3
