Given a sorted doubly linked list of distinct nodes(no two nodes have the same data) and a value x. The task is to count the triplets in the list that product up to a given value x.
Examples:
Input: list = 1->2->4->5->6->8->9, x = 8
Output: 1
Triplet is (1, 2, 4)Input: list = 1->2->4->5->6->8->9, x = 120
Output: 1
Triplet is (4, 5, 6)
Naive Approach: Using three nested loops generate all triplets and check whether elements in the triplet product up to x or not.
Below is the implementation of the above approach:
C++
// C++ implementation to count triplets// in a sorted doubly linked list// whose product is equal to a given value 'x'#include <bits/stdc++.h>using namespace std;// structure of node of doubly linked liststruct Node { int data; struct Node *next, *prev;};// function to count triplets in a sorted doubly linked list// whose product is equal to a given value 'x'int countTriplets(struct Node* head, int x){ struct Node *ptr1, *ptr2, *ptr3; int count = 0; // generate all possible triplets for (ptr1 = head; ptr1 != NULL; ptr1 = ptr1->next) for (ptr2 = ptr1->next; ptr2 != NULL; ptr2 = ptr2->next) for (ptr3 = ptr2->next; ptr3 != NULL; ptr3 = ptr3->next) // if elements in the current triplet product up to 'x' if ((ptr1->data * ptr2->data * ptr3->data) == x) // increment count count++; // required count of triplets return count;}// A utility function to insert a new node at the// beginning of doubly linked listvoid insert(struct Node** head, int data){ // allocate node struct Node* temp = new Node(); // put in the data temp->data = data; temp->next = temp->prev = NULL; if ((*head) == NULL) (*head) = temp; else { temp->next = *head; (*head)->prev = temp; (*head) = temp; }}// Driver program to test aboveint main(){ // start with an empty doubly linked list struct Node* head = NULL; // insert values in sorted order insert(&head, 9); insert(&head, 8); insert(&head, 6); insert(&head, 5); insert(&head, 4); insert(&head, 2); insert(&head, 1); int x = 8; cout << "Count = " << countTriplets(head, x); return 0;} |
Java
// Java implementation to count triplets // in a sorted doubly linked list // whose sum is equal to a given value 'x' import java.util.*;// Represents node of a doubly linked list class Node { public int data; public Node prev, next; public Node(int val) { data = val; prev = null; next = null; } } class GFG { // function to count triplets in // a sorted doubly linked list // whose sum is equal to a given value 'x' static int countTriplets(Node head, int x) { Node ptr1, ptr2, ptr3; int count = 0; // generate all possible triplets for (ptr1 = head; ptr1 != null; ptr1 = ptr1.next) for (ptr2 = ptr1.next; ptr2 != null; ptr2 = ptr2.next) for (ptr3 = ptr2.next; ptr3 != null; ptr3 = ptr3.next) // if elements in the current triplet sum up to 'x' if ((ptr1.data * ptr2.data * ptr3.data) == x) // increment count count++; // required count of triplets return count; } // A utility function to insert a new node at the // beginning of doubly linked list static Node insert(Node head, int val) { // allocate node Node temp = new Node(val); if (head == null) head = temp; else { temp.next = head; head.prev = temp; head = temp; } return head; } // Driver code public static void main(String []args) { // start with an empty doubly linked list Node head = null; // insert values in sorted order 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; System.out.println("count = " + countTriplets(head, x)); } }// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to count triplets# in a sorted doubly linked list# whose sum is equal to a given value 'x'# Represents node of a doubly linked listclass Node: data = None prev = None next_ = None def __init__(self, val): self.data = val self.prev = None self.next_ = None# function to count triplets in# a sorted doubly linked list# whose sum is equal to a given value 'x'def countTriplets(head, x): ptr1, ptr2, ptr3 = Node(0), Node(0), Node(0) count = 0 # generate all possible triplets ptr1 = head while ptr1 is not None: ptr2 = ptr1.next_ while ptr2 is not None: ptr3 = ptr2.next_ while ptr3 is not None: # if elements in the current # triplet sum up to 'x' if ptr1.data * ptr2.data * ptr3.data == x: # increment count count += 1 ptr3 = ptr3.next_ ptr2 = ptr2.next_ ptr1 = ptr1.next_ # required count of triplets return count# A utility function to insert a new node at the# beginning of doubly linked listdef insert(head, val): # allocate node temp = Node(val) if head is None: head = temp else: temp.next_ = head head.prev = temp head = temp return head# Driver Codeif __name__ == "__main__": # start with an empty doubly linked list head = Node(0) # insert values in sorted order 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 print("count =", countTriplets(head, x))# This code is contributed by# sanjeev2552 |
C#
// C# implementation to count triplets // in a sorted doubly linked list // whose sum is equal to a given value 'x' using System; // Represents node of a doubly linked list public class Node { public int data; public Node prev, next; public Node(int val) { data = val; prev = null; next = null; } } class GFG { // function to count triplets in // a sorted doubly linked list // whose sum is equal to a given value 'x' static int countTriplets(Node head, int x) { Node ptr1, ptr2, ptr3; int count = 0; // generate all possible triplets for (ptr1 = head; ptr1 != null; ptr1 = ptr1.next) for (ptr2 = ptr1.next; ptr2 != null; ptr2 = ptr2.next) for (ptr3 = ptr2.next; ptr3 != null; ptr3 = ptr3.next) // if elements in the current triplet sum up to 'x' if ((ptr1.data * ptr2.data * ptr3.data) == x) // increment count count++; // required count of triplets return count; } // A utility function to insert a new node at the // beginning of doubly linked list static Node insert(Node head, int val) { // allocate node Node temp = new Node(val); if (head == null) head = temp; else { temp.next = head; head.prev = temp; head = temp; } return head; } // Driver code public static void Main(String []args) { // start with an empty doubly linked list Node head = null; // insert values in sorted order 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; Console.WriteLine("count = " + countTriplets(head, x)); } } // This code is contributed by Arnab Kundu |
Javascript
<script>// javascript implementation to count triplets // in a sorted doubly linked list // whose sum is equal to a given value 'x' // Represents node of a doubly linked list class Node { constructor(val) { this.data = val; this.prev = null; this.next = null; }} // function to count triplets in // a sorted doubly linked list // whose sum is equal to a given value 'x' function countTriplets( head , x) { var ptr1, ptr2, ptr3; var count = 0; // generate all possible triplets for (ptr1 = head; ptr1 != null; ptr1 = ptr1.next) for (ptr2 = ptr1.next; ptr2 != null; ptr2 = ptr2.next) for (ptr3 = ptr2.next; ptr3 != null; ptr3 = ptr3.next) // if elements in the current triplet sum up to 'x' if ((ptr1.data * ptr2.data * ptr3.data) == x) // increment count count++; // required count of triplets return count; } // A utility function to insert a new node at the // beginning of doubly linked list function insert( head , val) { // allocate node temp = new Node(val); if (head == null) head = temp; else { temp.next = head; head.prev = temp; head = temp; } return head; } // Driver code // start with an empty doubly linked list head = null; // insert values in sorted order 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; document.write("count = " + countTriplets(head, x));// This code contributed by umadevi9616 </script> |
Output:
Count = 1
Complexity Analysis:
- Time Complexity: O(n^3)
- Auxiliary Space: O(1)
Method-2 (Hashing):
Create a hash table with (key, value) tuples represented as (node data, node pointer) tuples. Traverse the doubly linked list and store each node’s data and its pointer pair(tuple) in the hash table. Now, generate each possible pair of nodes. For each pair of nodes, calculate the p_product(product of data in the two nodes) and check whether (x/p_product) exists in the hash table or not.
If it exists, then also verify that the two nodes in the pair are not same as to the node associated with (x/p_product) in the hash table and finally increment count. Return (count / 3) as each triplet is counted 3 times in the above process.
Below is the implementation of the above approach:
C++
// C++ implementation to count triplets// in a sorted doubly linked list// whose product is equal to a given value 'x'#include <bits/stdc++.h>using namespace std;// structure of node of doubly linked liststruct Node { int data; struct Node *next, *prev;};// function to count triplets in a sorted doubly linked list// whose product is equal to a given value 'x'int countTriplets(struct Node* head, int x){ struct Node *ptr, *ptr1, *ptr2; int count = 0; // unordered_map 'um' implemented as hash table unordered_map<int, Node*> um; // insert the <node data, node pointer> tuple in 'um' for (ptr = head; ptr != NULL; ptr = ptr->next) um[ptr->data] = ptr; // generate all possible pairs for (ptr1 = head; ptr1 != NULL; ptr1 = ptr1->next) for (ptr2 = ptr1->next; ptr2 != NULL; ptr2 = ptr2->next) { // p_product = product of elements in the current pair int p_product = (ptr1->data * ptr2->data); // if 'x/p_product' is present in 'um' and // either of the two nodes // are not equal to the 'um[x/p_product]' node if (um.find(x / p_product) != um.end() && um[x / p_product] != ptr1 && um[x / p_product] != ptr2) // increment count count++; } // required count of triplets // division by 3 as each triplet is counted 3 times return (count / 3);}// A utility function to insert a new node at the// beginning of doubly linked listvoid insert(struct Node** head, int data){ // allocate node struct Node* temp = new Node(); // put in the data temp->data = data; temp->next = temp->prev = NULL; if ((*head) == NULL) (*head) = temp; else { temp->next = *head; (*head)->prev = temp; (*head) = temp; }}// Driver program to test above functionsint main(){ // start with an empty doubly linked list struct Node* head = NULL; // insert values in sorted order insert(&head, 9); insert(&head, 8); insert(&head, 6); insert(&head, 5); insert(&head, 4); insert(&head, 2); insert(&head, 1); int x = 8; cout << "Count = " << countTriplets(head, x); return 0;} |
Java
// Java implementation to count triplets// in a sorted doubly linked list whose // product is equal to a given value 'x'import java.io.*;import java.util.*;// Structure of node of doubly linked listclass Node{ int data; Node next, prev;}class GFG{ // Function to count triplets in a sorted// doubly linked list whose product is // equal to a given value 'x'static int countTriplets(Node head, int x){ Node ptr, ptr1, ptr2; int count = 0; // Unordered_map 'um' implemented // as hash table Map<Integer, Node> um = new HashMap<Integer, Node>(); // Insert the <node data, node pointer> // tuple in 'um' for(ptr = head; ptr != null; ptr = ptr.next) { um.put(ptr.data, ptr); } // Generate all possible pairs for(ptr1 = head; ptr1 != null; ptr1 = ptr1.next) { for(ptr2 = ptr1.next; ptr2 != null; ptr2 = ptr2.next) { // p_product = product of elements // in the current pair int p_product = (ptr1.data * ptr2.data); // If 'x/p_product' is present in 'um' and // either of the two nodes are not equal // to the 'um[x/p_product]' node if (um.containsKey(x / p_product) && um.get(x / p_product) != ptr1 && um.get(x / p_product) != ptr2) { // Increment count count++; } } } // Required count of triplets // division by 3 as each triplet // is counted 3 times return (count / 3);}// A utility function to insert a new // node at the beginning of doubly linked liststatic Node insert(Node head, int data){ // Allocate node Node temp = new Node(); // Put in the data 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 codepublic static void main(String[] args) { // Start with an empty doubly linked list Node head = null; // Insert values in sorted order 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; System.out.println("Count = " + countTriplets(head, x));}}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 implementation to # count triplets in a sorted # doubly linked list whose # product is equal to a given # value 'x'from math import ceil# structure of node of doubly # linked listclass Node: def __init__(self, x): self.data = x self.next = None self.prev = None# function to count triplets # in a sorted doubly linked # list whose product is equal # to a given value 'x'def countTriplets(head, x): ptr, ptr1, ptr2 = None, None, None count = 0 # unordered_map 'um' implemented # as hash table um = {} # insert the tuple in 'um' ptr = head while ptr != None: um[ptr.data] = ptr ptr = ptr.next # generate all possible pairs ptr1 = head while ptr1 != None: ptr2 = ptr1.next while ptr2 != None: # p_product = product of # elements in the current # pair p_product = (ptr1.data * ptr2.data) # if 'x/p_product' is present # in 'um' and either of the # two nodes are not equal to # the 'um[x/p_product]' node if ((x / p_product) in um and (x / p_product) != ptr1 and um[x / p_product] != ptr2): # increment count count += 1 ptr2 = ptr2.next ptr1 = ptr1.next # required count of triplets # division by 3 as each triplet # is counted 3 times return (count // 3)# A utility function to insert a # new node at the beginning of # doubly linked listdef insert(head, data): # allocate node temp = Node(data) # put in the data 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__': # start with an empty # doubly linked list head = None # insert values in sorted # order 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 print("Count =", countTriplets(head, x))# This code is contributed by Mohit Kumar 29 |
C#
// C# implementation to count triplets// in a sorted doubly linked list whose // product is equal to a given value 'x'using System;using System.Collections.Generic;// Structure of node of doubly linked listclass Node{ public int data; public Node next, prev;}class GFG{// Function to count triplets in a sorted// doubly linked list whose product is // equal to a given value 'x'static int countTriplets(Node head, int x){ Node ptr, ptr1, ptr2; int count = 0; // Unordered_map 'um' implemented // as hash table Dictionary<int, Node> um = new Dictionary<int, Node>(); // Insert the <node data, node pointer> // tuple in 'um' for(ptr = head; ptr != null; ptr = ptr.next) { um.Add(ptr.data, ptr); } // Generate all possible pairs for(ptr1 = head; ptr1 != null; ptr1 = ptr1.next) { for(ptr2 = ptr1.next; ptr2 != null; ptr2 = ptr2.next) { // p_product = product of elements // in the current pair int p_product = (ptr1.data * ptr2.data); // If 'x/p_product' is present in 'um' and // either of the two nodes are not equal // to the 'um[x/p_product]' node if (um.ContainsKey(x / p_product) && um[x / p_product] != ptr1 && um[x / p_product] != ptr2) { // Increment count count++; } } } // Required count of triplets // division by 3 as each triplet // is counted 3 times return (count / 3);}// A utility function to insert a new // node at the beginning of doubly linked liststatic Node insert(Node head, int data){ // Allocate node Node temp = new Node(); // Put in the data 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 static public void Main (){ // Start with an empty doubly linked list Node head = null; // Insert values in sorted order 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; Console.WriteLine("Count = " + countTriplets(head, x));}}// This code is contributed by rag2127 |
Javascript
<script>// JavaScript implementation to count triplets// in a sorted doubly linked list whose// product is equal to a given value 'x'class Node{ constructor(data) { this.data=data; this.next=this.prev=null; }}// Function to count triplets in a sorted// doubly linked list whose product is// equal to a given value 'x'function countTriplets(head,x){ let ptr, ptr1, ptr2; let count = 0; // Unordered_map 'um' implemented // as hash table let um = new Map(); // Insert the <node data, node pointer> // tuple in 'um' for(ptr = head; ptr != null; ptr = ptr.next) { um.set(ptr.data, ptr); } // Generate all possible pairs for(ptr1 = head; ptr1 != null; ptr1 = ptr1.next) { for(ptr2 = ptr1.next; ptr2 != null; ptr2 = ptr2.next) { // p_product = product of elements // in the current pair let p_product = (ptr1.data * ptr2.data); // If 'x/p_product' is present in 'um' and // either of the two nodes are not equal // to the 'um[x/p_product]' node if (um.has(x / p_product) && um.get(x / p_product) != ptr1 && um.get(x / p_product) != ptr2) { // Increment count count++; } } } // Required count of triplets // division by 3 as each triplet // is counted 3 times return (count / 3);}// A utility function to insert a new// node at the beginning of doubly linked listfunction insert(head,data){ // Allocate node let temp = new Node(); // Put in the data 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// Start with an empty doubly linked listlet head = null;// Insert values in sorted orderhead = 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);let x = 8;document.write("Count = " + countTriplets(head, x));// This code is contributed by patel2127</script> |
Output:
Count = 1
Complexity Analysis:
- Time Complexity: O(n^2)
- Auxiliary Space: O(n)
Method-3 (Use of two pointers):
Traverse the doubly linked list from left to right. For each current node during the traversal, initialize two pointers first = pointer to the node next to the current node and last = pointer to the last node of the list. Now, count pairs in the list from first to the last pointer that product up to the value (x / current node’s data) (algorithm described in this post). Add this count to the total_count of triplets. Pointer to the last node can be found only once in the beginning.
Below is the implementation of the above approach:
C++
// C++ implementation to count triplets// in a sorted doubly linked list// whose product is equal to a given value 'x'#include <bits/stdc++.h>using namespace std;// structure of node of doubly linked liststruct Node { int data; struct Node *next, *prev;};// function to count pairs whose product equal to given 'value'int countPairs(struct Node* first, struct Node* second, int value){ int count = 0; // 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) == value) { // increment count count++; // move first in forward direction first = first->next; // move second in backward direction second = second->prev; } // if product is greater than 'value' // move second in backward direction else if ((first->data * second->data) > value) second = second->prev; // else move first in forward direction else first = first->next; } // required count of pairs return count;}// function to count triplets in a sorted doubly linked list// whose product is equal to a given value 'x'int countTriplets(struct Node* head, int x){ // if list is empty if (head == NULL) return 0; struct Node *current, *first, *last; int count = 0; // get pointer to the last node of // the doubly linked list last = head; while (last->next != NULL) last = last->next; // traversing the doubly linked list for (current = head; current != NULL; current = current->next) { // for each current node first = current->next; // count pairs with product(x / current->data) in the range // first to last and add it to the 'count' of triplets count += countPairs(first, last, x / current->data); } // required count of triplets return count;}// A utility function to insert a new node at the// beginning of doubly linked listvoid insert(struct Node** head, int data){ // allocate node struct Node* temp = new Node(); // put in the data temp->data = data; temp->next = temp->prev = NULL; if ((*head) == NULL) (*head) = temp; else { temp->next = *head; (*head)->prev = temp; (*head) = temp; }}// Driver program to test aboveint main(){ // start with an empty doubly linked list struct Node* head = NULL; // insert values in sorted order insert(&head, 9); insert(&head, 8); insert(&head, 6); insert(&head, 5); insert(&head, 4); insert(&head, 2); insert(&head, 1); int x = 8; cout << "Count = " << countTriplets(head, x); return 0;} |
Java
// Java implementation to count triplets// in a sorted doubly linked list// whose product is equal to a given value 'x'import java.util.*;class GFG{ // structure of node of doubly linked liststatic class Node { int data; Node next, prev;};// function to count pairs whose product// equal to given 'value'static int countPairs(Node first, Node second, int value){ int count = 0; // 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) == value) { // increment count count++; // move first in forward direction first = first.next; // move second in backward direction second = second.prev; } // if product is greater than 'value' // move second in backward direction else if ((first.data * second.data) > value) second = second.prev; // else move first in forward direction else first = first.next; } // required count of pairs return count;}// function to count triplets in // a sorted doubly linked list// whose product is equal to a given value 'x'static int countTriplets(Node head, int x){ // if list is empty if (head == null) return 0; Node current, first, last; int count = 0; // get pointer to the last node of // the doubly linked list last = head; while (last.next != null) last = last.next; // traversing the doubly linked list for (current = head; current != null; current = current.next) { // for each current node first = current.next; // count pairs with product(x / current.data) // in the range first to last and // add it to the 'count' of triplets count += countPairs(first, last, x / current.data); } // required count of triplets return count;}// A utility function to insert a new node at the// beginning of doubly linked liststatic Node insert(Node head, int data){ // allocate node Node temp = new Node(); // put in the data 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 codepublic static void main(String args[]){ // start with an empty doubly linked list Node head = null; // insert values in sorted order 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; System.out.println( "Count = "+ countTriplets(head, x));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation to count triplets# in a sorted doubly linked list whose# product is equal to a given value 'x' # Structure of node of doubly linked listclass Node: def __init__(self, data): self.data = data self.next = None self.prev = None# Function to count pairs whose product# equal to given 'value'def countPairs(first, second, value): count = 0 # 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) == value): # Increment count count += 1 # Move first in forward direction first = first.next # Move second in backward direction second = second.prev # If product is greater than 'value' # move second in backward direction elif ((first.data * second.data) > value): second = second.prev # Else move first in forward direction else: first = first.next # Required count of pairs return count # Function to count triplets in a sorted# doubly linked list whose product is # equal to a given value 'x'def countTriplets(head, x): # If list is empty if (head == None): return 0 count = 0 # Get pointer to the last node of # the doubly linked list last = head while (last.next != None): last = last.next current = head # Traversing the doubly linked list while current != None: # For each current node first = current.next # Count pairs with product(x / current.data) # in the range first to last and # add it to the 'count' of triplets count += countPairs(first, last, x // current.data) current = current.next # Required count of triplets return count# A utility function to insert a new node# at the beginning of doubly linked listdef insert(head, data): # Allocate node temp = Node(data) # Put in the data 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__': # Start with an empty doubly linked list head = None # Insert values in sorted order 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 print( "Count = " + str(countTriplets(head, x)))# This code is contributed by rutvik_56 |
C#
// C# implementation to count triplets// in a sorted doubly linked list// whose product is equal to a given value 'x'using System;class GFG{ // structure of node of doubly linked listclass Node { public int data; public Node next, prev;}; // function to count pairs whose product// equal to given 'value'static int countPairs(Node first, Node second, int value){ int count = 0; // 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) == value) { // increment count count++; // move first in forward direction first = first.next; // move second in backward direction second = second.prev; } // if product is greater than 'value' // move second in backward direction else if ((first.data * second.data) > value) second = second.prev; // else move first in forward direction else first = first.next; } // required count of pairs return count;} // function to count triplets in // a sorted doubly linked list// whose product is equal to a given value 'x'static int countTriplets(Node head, int x){ // if list is empty if (head == null) return 0; Node current, first, last; int count = 0; // get pointer to the last node of // the doubly linked list last = head; while (last.next != null) last = last.next; // traversing the doubly linked list for (current = head; current != null; current = current.next) { // for each current node first = current.next; // count pairs with product(x / current.data) // in the range first to last and // add it to the 'count' of triplets count += countPairs(first, last, x / current.data); } // required count of triplets return count;} // A utility function to insert a new node at the// beginning of doubly linked liststatic Node insert(Node head, int data){ // allocate node Node temp = new Node(); // put in the data 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 codepublic static void Main(String []args){ // start with an empty doubly linked list Node head = null; // insert values in sorted order 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; Console.WriteLine( "Count = "+ countTriplets(head, x));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation to count triplets// in a sorted doubly linked list// whose product is equal to a given value 'x'// structure of node of doubly linked listclass Node{ constructor() { let data; let next, prev; }}// function to count pairs whose product// equal to given 'value'function countPairs(first,second,value){ let count = 0; // 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) == value) { // increment count count++; // move first in forward direction first = first.next; // move second in backward direction second = second.prev; } // if product is greater than 'value' // move second in backward direction else if ((first.data * second.data) > value) second = second.prev; // else move first in forward direction else first = first.next; } // required count of pairs return count;}// function to count triplets in// a sorted doubly linked list// whose product is equal to a given value 'x'function countTriplets(head,x){ // if list is empty if (head == null) return 0; let current, first, last; let count = 0; // get pointer to the last node of // the doubly linked list last = head; while (last.next != null) last = last.next; // traversing the doubly linked list for (current = head; current != null; current = current.next) { // for each current node first = current.next; // count pairs with product(x / current.data) // in the range first to last and // add it to the 'count' of triplets count += countPairs(first, last, x / current.data); } // required count of triplets return count;}// A utility function to insert a new node at the// beginning of doubly linked listfunction insert(head,data){ // allocate node let temp = new Node(); // put in the data 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// start with an empty doubly linked listlet head = null;// insert values in sorted orderhead = 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);let x = 8;document.write( "Count = "+ countTriplets(head, x)); // This code is contributed by unknown2108</script> |
Output:
Count = 1
Complexity Analysis:
- Time Complexity: O(n^2)
- 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!
