मान लीजिए हमारे पास अद्वितीय धनात्मक संख्याओं की एक क्रमबद्ध डबल लिंक्ड सूची है; हमें डबल लिंक्ड सूची में उन जोड़ों को ढूंढना है जिनका गुणनफल दिए गए मान x के समान है। हमें इस बात का ध्यान रखना है कि यह बिना किसी अतिरिक्त स्थान का उपभोग किए हल किया जाएगा।
तो, यदि इनपुट L = 1 ⇄ 2 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 8 ⇄ 9 और x = 8 की तरह है, तो आउटपुट (1, 8), (2, 4) होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
curr := head, nxt := head
जब nxt.next, None नहीं है, तब तक करें
nxt := nxt.next
found := False
जब curr और nxt null नहीं हैं और curr और nxt अलग हैं और nxt.next, curr नहीं है, तब तक करें
यदि (curr.data * nxt.data), x के समान है, तो
found := True
एक जोड़ी curr.data, nxt.data प्रदर्शित करें
curr := curr.next
nxt := nxt.prev
अन्यथा,
यदि (curr.data * nxt.data) < x, तो
curr := curr.next
अन्यथा,
nxt := nxt.prev
यदि found, False है, तो
"Not found" प्रदर्शित करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
class ListNode: def __init__(self, data): self.data = data self.prev = None self.next = None def insert(head, data): node = ListNode(0) node.data = data node.next = node.prev = None if (head == None): (head) = node else : node.next = head head.prev = node head = node return head def get_pair_prod(head, x): curr = head nxt = head while (nxt.next != None): nxt = nxt.next found = False while (curr != None and nxt != None and curr != nxt and nxt.next != curr) : if ((curr.data * nxt.data) == x) : found = True print("(", curr.data, ", ", nxt.data, ")") curr = curr.next nxt = nxt.prev else : if ((curr.data * nxt.data) < x): curr = curr.next else: nxt = nxt.prev if (found == False): print("Not found") head = None head = insert(head, 9) head = insert(head, 8) head = insert(head, 6) head = insert(head, 5) head = insert(head, 4) head = insert(head, 2) head = insert(head, 1) x = 8 get_pair_prod(head, x) इनपुट
head = None head = insert(head, 9) head = insert(head, 8) head = insert(head, 6) head = insert(head, 5) head = insert(head, 4) head = insert(head, 2) head = insert(head, 1) x = 8
आउटपुट
( 1 , 8 ) ( 2 , 4 )
