समस्या विवरण
एक लिंक्ड लिस्ट दी गई है जिसमें डुप्लिकेट तत्व हो सकते हैं। हमें उन तत्वों की गिनती करनी है जिनकी आवृत्ति (frequency) न्यूनतम है।
उदाहरण
इनपुट: 1→1→2→2→2→3→3
आउटपुट: 2
व्याख्या: न्यूनतम आवृत्ति 2 है (तत्व 1 और 3 की), इसलिए गिनती 2 है।
इनपुट: 1→2→3→2→4→2→5
आउटपुट: 4
व्याख्या: न्यूनतम आवृत्ति 1 है (तत्व 1, 3, 4, 5 की), इसलिए गिनती 4 है।
समाधान दृष्टिकोण
- लिंक्ड लिस्ट को पार करके प्रत्येक तत्व की आवृत्ति अनऑर्डर्ड मैप (unordered_map) में संग्रहीत करें।
- मैप से न्यूनतम आवृत्ति मान ढूंढें।
- उन तत्वों की गिनती करें जिनकी आवृत्ति इस न्यूनतम के बराबर है।
- उस गिनती को लौटाएं।
कार्यकारी प्रोग्राम
#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;
struct Node {
int key;
Node* next;
};
void push(Node** head_ref, int new_key) {
Node* new_node = new Node;
new_node->key = new_key;
new_node->next = *head_ref;
*head_ref = new_node;
}
int countMinFrequency(Node* head) {
unordered_map<int, int> freq;
Node* curr = head;
while (curr) {
freq[curr->key]++;
curr = curr->next;
}
int minFreq = INT_MAX;
for (auto& p : freq) {
minFreq = min(minFreq, p.second);
}
int count = 0;
for (auto& p : freq) {
if (p.second == minFreq) count += p.second; // या count++ यदि अद्वितीय तत्व गिनने हैं
}
return count;
}
int main() {
Node* head = NULL;
push(&head, 30);
push(&head, 50);
push(&head, 61);
push(&head, 40);
push(&head, 30);
cout << "न्यूनतम आवृत्ति वाले तत्वों की गिनती: " << countMinFrequency(head);
return 0;
}
आउटपुट
न्यूनतम आवृत्ति वाले तत्वों की गिनती: 3
