Count triplets in a sorted doubly linked list whose product is equal to a given value x | C ++ 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 list ; function to count triplets in a sorted doubly linked list whose product is equal to a given value ' x ' ; unordered_map ' um ' implemented as hash table ; insert the < node data , node pointer > tuple in ' um ' ; generate all possible pairs ; p_product = product of elements in the current pair ; if ' x / p _ product ' is present in ' um ' and either of the two nodes are not equal to the ' um [ x / p _ product ] ' node ; increment count ; required count of triplets division by 3 as each triplet is counted 3 times ; A utility function to insert a new node at the beginning of doubly linked list ; allocate node ; put in the data ; Driver program to test above functions ; start with an empty doubly linked list ; insert values in sorted order
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next , * prev ; } ; int countTriplets ( struct Node * head , int x ) { struct Node * ptr , * ptr1 , * ptr2 ; int count = 0 ; unordered_map < int , Node * > um ; for ( ptr = head ; ptr != NULL ; ptr = ptr -> next ) um [ ptr -> data ] = ptr ; for ( ptr1 = head ; ptr1 != NULL ; ptr1 = ptr1 -> next ) for ( ptr2 = ptr1 -> next ; ptr2 != NULL ; ptr2 = ptr2 -> next ) { int p_product = ( ptr1 -> data * ptr2 -> data ) ; if ( um . find ( x / p_product ) != um . end ( ) && um [ x / p_product ] != ptr1 && um [ x / p_product ] != ptr2 ) count ++ ; } return ( count / 3 ) ; } void insert ( struct Node * * head , int data ) { struct 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 ; } } int main ( ) { 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 ; cout << " Count ▁ = ▁ " << countTriplets ( head , x ) ; return 0 ; }