পাইথনে সর্টেড ডাবলি লিঙ্কড লিস্টে দেওয়া গুণফলের জোড়া বের করা

ধরা যাক একটি সর্টেড ডাবলি লিঙ্কড লিস্ট আছে যাতে ইউনিক পজিটিভ নম্বর রয়েছে। আমাদের এই লিস্ট থেকে এমন জোড়া বের করতে হবে যাদের গুণফল একটি দেওয়া মান x-এর সমান। এটি এক্সট্রা স্পেস ছাড়া সমাধান করতে হবে।

যেমন, ইনপুট L = 1 ⇄ 2 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 8 ⇄ 9 এবং x = 8 হলে আউটপুট হবে (1, 8), (2, 4)।

সমাধানের ধাপসমূহ

• curr := head, nxt := head
• while nxt.next != None: nxt := nxt.next (শেষ নোডে যান)
• found := False
• while curr এবং nxt নাল নন এবং curr != nxt এবং nxt.next != curr:
  • যদি curr.data * nxt.data == x হয়:
    • found := True
    • জোড়া প্রিন্ট করুন
    • curr := curr.next, nxt := nxt.prev
  • অন্যথায় যদি গুণফল < 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 )