Given a sorted doubly linked list of positive distinct elements, the task is to find pairs in the doubly linked list whose product is equal to given value x, without using any extra space.
Examples:
Input : List = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9
x = 8
Output: (1, 8), (2, 4)
Input : List = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7
x = 6
Output: (1, 6), (2, 3)
A Simple Approach for this problem is to traverse the linked list using two nested loops and find all pairs and check for the pairs with product equals to x. Time complexity for this problem will be O(n^2), n is total number of nodes in doubly linked list.
An Efficient Solution for this problem is same as this article. Here is the algorithm :
- Initialize two pointer variables to find the candidate elements in the sorted doubly linked list. Initialize first with start of doubly linked list i.e; first=head and initialize second with last node of doubly linked list i.e; second=last_node.
- We initialize first and second pointers as first and last nodes. Here we don’t have random access, so to find second pointer, we traverse the list to initialize second.
- If current product of first and second is less than x, then we move first in forward direction. If current product of first and second element is greater than x, then we move second in backward direction.
- Loop termination conditions are also different from arrays. The loop terminates when either of two pointers become NULL, or they cross each other (second->next = first), or they become same (first == second)
Below is the implementation of the above approach:
C++
// C++ program to find a pair with// given product x in sorted Doubly// Linked List#include <bits/stdc++.h>using namespace std;// Doubly Linked List Nodestruct Node { int data; struct Node *next, *prev;};// Function to find pair whose product// equal to given value xvoid pairProduct(struct Node* head, int x){ // Set two pointers, // first to the beginning of DLL // and second to the end of DLL. struct Node* first = head; struct Node* second = head; while (second->next != NULL) second = second->next; // To track if we find a pair or not bool found = false; // The loop terminates when either of two pointers // become NULL, or they cross each other (second->next // == first), or they become same (first == second) while (first != NULL && second != NULL && first != second && second->next != first) { // pair found if ((first->data * second->data) == x) { found = true; cout << "(" << first->data << ", " << second->data << ")" << endl; // move first in forward direction first = first->next; // move second in backward direction second = second->prev; } else { if ((first->data * second->data) < x) first = first->next; else second = second->prev; } } // if pair is not present if (found == false) cout << "No pair found";}// A utility function to insert a new node at the// beginning of doubly linked listvoid 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; }}// Driver Codeint main(){ // Create Doubly Linked List struct 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;} |
Java
// Java program to find a pair with// given product x in sorted Doubly// Linked Listclass GFG { // Doubly Linked List Node static class Node { int data; Node next, prev; }; // Function to find pair whose product // equal to given value x static void pairProduct(Node head, int x) { // Set two pointers, // first to the beginning of DLL // and second to the end of DLL. Node first = head; Node second = head; while (second.next != null) second = second.next; // To track if we find a pair or not boolean found = false; // The loop terminates when either of two pointers // become null, or they cross each other (second.next // == first), or they become same (first == second) while (first != null && second != null && first != second && second.next != first) { // pair found if ((first.data * second.data) == x) { found = true; System.out.println("(" + first.data + ", " + second.data + ")"); // move first in forward direction first = first.next; // move second in backward direction second = second.prev; } else { if ((first.data * second.data) < x) first = first.next; else second = second.prev; } } // if pair is not present if (found == false) System.out.println("No pair found"); } // A utility function to insert a new node at the // beginning of doubly linked list static Node insert(Node head, int data) { Node temp = new Node(); temp.data = data; temp.next = temp.prev = null; if ((head) == null) (head) = temp; else { temp.next = head; (head).prev = temp; (head) = temp; } return head; } // Driver Code public static void main(String args[]) { // Create Doubly Linked List Node head = null; 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); int x = 8; pairProduct(head, x); }}// This code is contributed by Arnab Kundu |
Python3
# Python3 program to find a pair with# given product x in sorted Doubly# Linked List# Node of the doubly linked list class Node: def __init__(self, data): self.data = data self.prev = None self.next = None# Function to find pair whose product# equal to given value xdef pairProduct(head, x): # Set two pointers, # first to the beginning of DLL # and second to the end of DLL. first = head second = head while (second.next != None): second = second.next # To track if we find a pair or not found = False # The loop terminates when either of two pointers # become None, or they cross each other (second.next # == first), or they become same (first == second) while (first != None and second != None and first != second and second.next != first) : # pair found if ((first.data * second.data) == x) : found = True print("(", first.data, ", ", second.data, ")") # move first in forward direction first = first.next # move second in backward direction second = second.prev else : if ((first.data * second.data) < x): first = first.next else: second = second.prev # if pair is not present if (found == False): print( "No pair found")# A utility function to insert a new node at the# beginning of doubly linked listdef insert(head, data): temp = Node(0) temp.data = data temp.next = temp.prev = None if (head == None): (head) = temp else : temp.next = head (head).prev = temp (head) = temp return head# Driver Codeif __name__ == "__main__": # Create Doubly Linked List 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 pairProduct(head, x)# This code is contributed by Arnab Kundu |
C#
// C# program to find a pair with// given product x in sorted Doubly// Linked Listusing System;class GFG { // Doubly Linked List Node public class Node { public int data; public Node next, prev; }; // Function to find pair whose product // equal to given value x static void pairProduct(Node head, int x) { // Set two pointers, // first to the beginning of DLL // and second to the end of DLL. Node first = head; Node second = head; while (second.next != null) second = second.next; // To track if we find a pair or not bool found = false; // The loop terminates when either of two pointers // become null, or they cross each other (second.next // == first), or they become same (first == second) while (first != null && second != null && first != second && second.next != first) { // pair found if ((first.data * second.data) == x) { found = true; Console.WriteLine("(" + first.data + ", " + second.data + ")"); // move first in forward direction first = first.next; // move second in backward direction second = second.prev; } else { if ((first.data * second.data) < x) first = first.next; else second = second.prev; } } // if pair is not present if (found == false) Console.WriteLine("No pair found"); } // A utility function to insert a new node at the // beginning of doubly linked list static Node insert(Node head, int data) { Node temp = new Node(); temp.data = data; temp.next = temp.prev = null; if ((head) == null) (head) = temp; else { temp.next = head; (head).prev = temp; (head) = temp; } return head; } // Driver Code public static void Main(String[] args) { // Create Doubly Linked List Node head = null; 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); int x = 8; pairProduct(head, x); }}// This code contributed by Rajput-Ji |
Javascript
<script>// javascript program to find a pair with// given product x in sorted Doubly// Linked List // Doubly Linked List Nodeclass Node { constructor() { this.data = 0; this.prev = null; this.next = null; }} // Function to find pair whose product // equal to given value x function pairProduct( head , x) { // Set two pointers, // first to the beginning of DLL // and second to the end of DLL. first = head; second = head; while (second.next != null) second = second.next; // To track if we find a pair or not var found = false; // The loop terminates when either of two pointers // become null, or they cross each other (second.next // == first), or they become same (first == second) while (first != null && second != null && first != second && second.next != first) { // pair found if ((first.data * second.data) == x) { found = true; document.write("(" + first.data + ", " + second.data + ")<br/>"); // move first in forward direction first = first.next; // move second in backward direction second = second.prev; } else { if ((first.data * second.data) < x) first = first.next; else second = second.prev; } } // if pair is not present if (found == false) document.write("No pair found"); } // A utility function to insert a new node at the // beginning of doubly linked list function insert( head , data) { temp = new Node(); temp.data = data; temp.next = temp.prev = null; if ((head) == null) (head) = temp; else { temp.next = head; (head).prev = temp; (head) = temp; } return head; } // Driver Code // Create Doubly Linked List head = null; 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); var x = 8; pairProduct(head, x);// This code contributed by aashish1995</script> |
Output
(1, 8) (2, 4)
Time complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
