একটি সর্টেড ডাবলি লিংকড লিস্ট (পজিটিভ ডিস্টINCT এলিমেন্ট) ও একটি মান x দেওয়া আছে। এক্সট্রা স্পেস ছাড়া সেই লিস্ট থেকে যেসব পেয়ারের গুণফল x হয় সেগুলো বের করতে হবে।
উদাহরণ
List: 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9, x = 8
আউটপুট: (1, 8), (2, 4)
অ্যালগরিদম (টু-পয়েন্টার)
first= হেড,second= টেইল।- যদি
first->data * second->data == xহয়, প্রিন্ট করুন এবংfirstফরওয়ার্ড,secondব্যাকওয়ার্ড যান। - যদি গুণফল
x-এর চেয়ে ছোট হয়,firstবামে নিন। - যদি বড় হয়,
secondডানে নিন। - লুপ বন্ধ হবে যখন পয়েন্টারগুলো ক্রস করবে বা NULL হবে।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *next, *prev;
};
void pairProduct(Node* head, int x) {
Node *first = head, *second = head;
while (second->next) second = second->next;
bool found = false;
while (first && second && first != second && second->next != first) {
long long prod = 1LL * first->data * second->data;
if (prod == x) {
cout << "(" << first->data << ", " << second->data << ")\n";
found = true;
first = first->next;
second = second->prev;
} else if (prod < x) {
first = first->next;
} else {
second = second->prev;
}
}
if (!found) cout << "No pair found\n";
}
void insert(Node** head, int data) {
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() {
Node* head = NULL;
insert(&head, 9); insert(&head, 8); insert(&head, 6);
insert(&head, 5); insert(&head, 4); insert(&head, 2); insert(&head, 1);
int x = 8;
pairProduct(head, x);
return 0;
}
আউটপুট: (1, 8) (2, 4)
