একটি লিংকড লিস্ট দেওয়া আছে যাতে ডুপ্লিকেট উপাদান রয়েছে। কাজ হল লিস্টে যেসব উপাদানের ফ্রিকোয়েন্সি (ঘনত্ব) ন্যূনতম, তাদের সংখ্যা বের করা।
লিংকড লিস্ট হল একটি ডেটা স্ট্রাকচার যেখানে ডেটা সিরিয়াল অর্ডারে সংরক্ষিত থাকে, প্রতিটি এলিমেন্ট পরবর্তী এলিমেন্টের সাথে লিংকড থাকে।
উদাহরণ
ইনপুট: 1→1→2→2→2→3→3
আউটপুট: 2
ব্যাখ্যা: ন্যূনতম ফ্রিকোয়েন্সি ২, এবং ১ ও ৩ এই ফ্রিকোয়েন্সিতে আছে। তাই কাউন্ট ২।
ইনপুট: 1→2→3→2→4→2→5
আউটপুট: 4
ব্যাখ্যা: ন্যূনতম ফ্রিকোয়েন্সি ১, এবং ১, ৩, ৪, ৫ - এই ৪টি এলিমেন্ট এই ফ্রিকোয়েন্সিতে আছে।
সমাধানের পদ্ধতি
- লিংকড লিস্ট ডিফাইন করুন এবং এলিমেন্ট পুশ করুন।
- একটি
unordered_mapব্যবহার করে প্রতিটি এলিমেন্টের ফ্রিকোয়েন্সি সংরক্ষণ করুন। - লিস্ট ট্রাভার্স করে ফ্রিকোয়েন্সি ম্যাপে আপডেট করুন।
- ন্যূনতম ফ্রিকোয়েন্সি বের করুন।
- ন্যূনতম ফ্রিকোয়েন্সি পাওয়া এলিমেন্টগুলোর সংখ্যা গণনা করুন।
প্রোগ্রাম উদাহরণ
#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;
struct Node {
int key;
struct Node* next;
};
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;
}
int minimum(struct Node* head) {
unordered_map<int, int> mymap;
struct Node* current = head;
// ফ্রিকোয়েন্সি সংগ্রহ
while (current != NULL) {
int value = current->key;
mymap[value]++;
current = current->next;
}
// ন্যূনতম ফ্রিকোয়েন্সি বের করা
int minFreq = INT_MAX;
for (auto it = mymap.begin(); it != mymap.end(); it++) {
if (it->second < minFreq)
minFreq = it->second;
}
// ন্যূনতম ফ্রিকোয়েন্সি পাওয়া এলিমেন্ট গণনা
int count = 0;
for (auto it = mymap.begin(); it != mymap.end(); it++) {
if (it->second == minFreq)
count += it->second;
}
return count;
}
int main() {
struct Node* head = NULL;
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
