Count triplets in a sorted doubly linked list whose product is equal to a given value x | 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 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 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 code ; start with an empty doubly linked list ; insert values in sorted order
' NEW_LINE from math import ceil NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . data = x NEW_LINE self . next = None NEW_LINE self . prev = None NEW_LINE DEDENT DEDENT ' NEW_LINE def countTriplets ( head , x ) : NEW_LINE INDENT ptr , ptr1 , ptr2 = None , None , None NEW_LINE count = 0 NEW_LINE um = { } NEW_LINE DEDENT ' NEW_LINE INDENT ptr = head NEW_LINE while ptr != None : NEW_LINE INDENT um [ ptr . data ] = ptr NEW_LINE ptr = ptr . next NEW_LINE DEDENT ptr1 = head NEW_LINE while ptr1 != None : NEW_LINE INDENT ptr2 = ptr1 . next NEW_LINE while ptr2 != None : NEW_LINE INDENT p_product = ( ptr1 . data * ptr2 . data ) NEW_LINE if ( ( x / p_product ) in um and ( x / p_product ) != ptr1 and um [ x / p_product ] != ptr2 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT ptr2 = ptr2 . next NEW_LINE DEDENT ptr1 = ptr1 . next NEW_LINE DEDENT return ( count // 3 ) NEW_LINE DEDENT def insert ( head , data ) : NEW_LINE INDENT temp = Node ( data ) NEW_LINE temp . data = data NEW_LINE temp . next = temp . prev = None NEW_LINE if ( head == None ) : NEW_LINE INDENT head = temp NEW_LINE DEDENT else : NEW_LINE INDENT temp . next = head NEW_LINE head . prev = temp NEW_LINE head = temp NEW_LINE DEDENT return head NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT head = None NEW_LINE head = insert ( head , 9 ) NEW_LINE head = insert ( head , 8 ) NEW_LINE head = insert ( head , 6 ) NEW_LINE head = insert ( head , 5 ) NEW_LINE head = insert ( head , 4 ) NEW_LINE head = insert ( head , 2 ) NEW_LINE head = insert ( head , 1 ) NEW_LINE x = 8 NEW_LINE print ( " Count ▁ = " , countTriplets ( head , x ) ) NEW_LINE DEDENT