समस्या विवरण
एक क्रमबद्ध डबल लिंक्ड सूची दी गई है जिसमें पूर्णांक मान हैं। लक्ष्य उन ट्रिपलेट को ढूंढना है जिनका योग दिए गए मान x के बराबर है। यदि इनपुट लिंक्ड सूची 3-4-1-2 है और x 6 है तो गिनती 1 होगी (ट्रिपलेट (3,1,2))।
उदाहरण
इनपुट
linked list: [3-4-13-5-10-10-0] x=20
आउटपुट
दिए गए योग x वाले ट्रिपलेट की संख्या: 2
व्याख्या
ट्रिपलेट होंगे: (3,4,13) और (10,10,0)
इनपुट
linked list: [4-3-1-5-2-4-2] x=8
आउटपुट
दिए गए योग x वाले ट्रिपलेट की संख्या: 6
व्याख्या
ट्रिपलेट होंगे: (4,3,1), (1,5,2), (3,1,4), (1,5,2), (4,2,2) और (2,4,2)
दृष्टिकोण
इस दृष्टिकोण में:
- हम लिंक्ड सूची नोड को संरचना के रूप में ले रहे हैं जिसमें int डेटा भाग और स्वयं-संदर्भी next और previous पॉइंटर हैं।
- फंक्शन
insert_node(struct block** head, int data)डेटा के साथ लिंक्ड सूची के हेड पर नोड जोड़ता है। - फंक्शन
sum_x(struct block* head, int x)डबल लिंक्ड सूची के हेड का पॉइंटर और पूर्णांकxलेता है और डेटा भाग का योगxके बराबर होने वाले नोड्स के ट्रिपलेट की संख्या लौटाता है। - प्रारंभिक गिनती 0 लें।
struct blockप्रकार के तीन पॉइंटरtemp_1,temp_2औरtemp_3लें।temp_1को लिंक्ड सूची के हेड पर इंगित करके शुरू करें,temp_2कोtemp_1के अगले पर औरtemp_3कोtemp_2के अगले पर इंगित करें, हमारे पास पहले तीन नोड्स पर इंगित करने वाले तीन पॉइंटर हैं।- अंतिम नोड तक इन पॉइंटर्स का उपयोग करके पार करें।
- यदि उपरोक्त सभी पॉइंटर्स के वर्तमान डेटा भागों का योग
xके बराबर है। ((temp_1->data + temp_2->data + temp_3->data) == x) तो गिनती बढ़ाएं। - अंत में हमने ट्रिपलेट की संख्या गिनी और
countमें संग्रहीत की। - परिणाम के रूप में गिनती लौटाएं।
C++ कोड उदाहरण
#include <iostream>
using namespace std;
struct block {
int data;
struct block *next, *prev;
};
void insert_node(struct block** head, int data) {
struct block* ptr = new block();
ptr->data = data;
ptr->next = NULL;
ptr->prev = NULL;
if ((*head) == NULL) {
(*head) = ptr;
} else {
ptr->next = *head;
(*head)->prev = ptr;
(*head) = ptr;
}
}
int sum_x(struct block* head, int x) {
int count = 0;
struct block *temp_1, *temp_2, *temp_3;
for (temp_1 = head; temp_1 != NULL; temp_1 = temp_1->next) {
for (temp_2 = temp_1->next; temp_2 != NULL; temp_2 = temp_2->next) {
for (temp_3 = temp_2->next; temp_3 != NULL; temp_3 = temp_3->next) {
if ((temp_1->data + temp_2->data + temp_3->data) == x) {
count++;
}
}
}
}
return count;
}
int main() {
struct block* head = NULL;
insert_node(&head, 200);
insert_node(&head, 100);
insert_node(&head, 16);
insert_node(&head, 14);
insert_node(&head, 10);
insert_node(&head, 10);
insert_node(&head, 2);
int x = 22;
cout << "दिए गए योग x वाले ट्रिपलेट की संख्या: " << sum_x(head, x);
return 0;
}
आउटपुट
दिए गए योग x वाले ट्रिपलेट की संख्या: 1
