ডাবলি লিংকড লিস্টে প্রদত্ত সমপূর্ণ যুগল খুঁজে বের করা C++-এ

এই সমস্যায়, আমাদের একটি ডাবলি লিংকড লিস্ট এবং একটি সম মান দেওয়া আছে। আমাদের কাজ হল ডাবলি লিংকড লিস্টে প্রদত্ত সমের যুগলগুলো খুঁজে বের করা।

উদাহরণ

ইনপুট

হেড → 2 ⇄ 5 ⇄ 6 ⇄ 9 ⇄ 12, x = 11

আউটপুট

(2, 9), (5, 6)

ব্যাখ্যা

(2, 9) যুগলের জন্য, মানগুলোর সম = 11
(5, 6) যুগলের জন্য, মানগুলোর সম = 11

সমাধানের পদ্ধতি

এই সমস্যার একটি সহজ সমাধান হল পুরো লিংকড লিস্টটি ট্রাভার্স করা এবং প্রতিটি এলিমেন্ট নেওয়া, তারপর বাকি লিংকড লিস্টে এমন এলিমেন্ট খুঁজে বের করা যার সাথে যোগফল প্রদত্ত সমের সমান হবে। এটি নেস্টেড লুপ ব্যবহার করে করা হয়।

প্রোগ্রাম উদাহরণ

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *next, *prev;
};

void findSumPairs(struct Node *head, int sum) {
    struct Node *first = head;
    int pairCount = 0;
    
    while (first != NULL) {
        struct Node *second = first->next;
        while(second != NULL){
            if ((first->data + second->data) == sum) {
                pairCount++;
                cout << "(" << first->data << ", " << second->data << ")\n";
            }
            second = second->next;
        }
        first = first->next;
    }
    
    if (!pairCount)
        cout << "No Such Pairs found!";
}

void insert(struct Node **head, int data) {
    struct Node *temp = new Node;
    temp->data = data;
    temp->next = temp->prev = NULL;
    
    if (!(*head))
        (*head) = temp;
    else{
        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}

int main() {
    struct Node *head = NULL;
    insert(&head, 12);
    insert(&head, 9);
    insert(&head, 6);
    insert(&head, 5);
    insert(&head, 2);
    
    int sum = 11;
    cout << "Pair in the linked list with sum = " << sum << " :\n";
    findSumPairs(head, sum);
    return 0;
}

আউটপুট

Pair in the linked list with sum = 11 : (2, 9) (5, 6)

একটি আরও কার্যকর পদ্ধতি হল লিংকড লিস্টটি সর্টেড থাকার সত্যটি ব্যবহার করা। এখানে আমরা دوটি পয়েন্টার ব্যবহার করব: একটি start যা প্রাথমিকভাবে লিংকড লিস্টের হেডে নির্দেশ করবে, এবং অন্যটি end যা লিংকড লিস্টের শেষ নোডে নির্দেশ করবে।

এখন, আমরা দুটি পয়েন্টারের মান যোগ করে sumVal বের করব এবং তারপর প্রদত্ত সমের সাথে তুলনা করব:

• যদি sumVal > sum হয়, end পয়েন্টারটিকে বাম দিকে সরাব।
• যদি sumVal < sum হয়, start পয়েন্টারটিকে ডান দিকে সরাব।
• যদি sumVal == sum হয়, দুটি মান প্রিন্ট করুন, start পয়েন্টারটিকে ডান দিকে এবং end পয়েন্টারটিকে বাম দিকে সরাব।

যখন পয়েন্টার দুটি একে অপরের সাথে ক্রস করবে, লুপ থেকে বের হয়ে যাব। এছাড়া, আমরা খুঁজে পাওয়া যুগল সংখ্যা গণনা করব, যদি সেটি ০ হয় তবে "No Such Pairs found!" প্রিন্ট করব।

অপ্টিমাইজড প্রোগ্রাম উদাহরণ

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *next, *prev;
};

void findSumPairs(struct Node *head, int sum) {
    struct Node *start = head;
    struct Node *end = head;
    
    // end পয়েন্টারকে শেষ নোডে নিয়ে যান
    while (end->next != NULL)
        end = end->next;
    
    int pairCount = 0;
    
    while (start != NULL && end != NULL && start != end && end->next != start) {
        if ((start->data + end->data) == sum) {
            pairCount++;
            cout << "(" << start->data << ", " << end->data << ")\n";
            start = start->next;
            end = end->prev;
        }
        else if ((start->data + end->data) < sum)
            start = start->next;
        else
            end = end->prev;
    }
    
    if (!pairCount)
        cout << "No Such Pairs found!";
}

void insert(struct Node **head, int data) {
    struct Node *temp = new Node;
    temp->data = data;
    temp->next = temp->prev = NULL;
    
    if (!(*head))
        (*head) = temp;
    else{
        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}

int main() {
    struct Node *head = NULL;
    insert(&head, 12);
    insert(&head, 9);
    insert(&head, 6);
    insert(&head, 5);
    insert(&head, 2);
    
    int sum = 11;
    cout << "Pair in the linked list with sum = " << sum << " :\n";
    findSumPairs(head, sum);
    return 0;
}

আউটপুট

Pair in the linked list with sum = 11 : (2, 9) (5, 6)