Count triplets in a sorted doubly linked list whose product is equal to a given value x | Java 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 code ; Start with an empty doubly linked list ; Insert values in sorted order
import java . io . * ; import java . util . * ; class Node { int data ; Node next , prev ; } class GFG { static int countTriplets ( Node head , int x ) { Node ptr , ptr1 , ptr2 ; int count = 0 ; Map < Integer , Node > um = new HashMap < Integer , Node > ( ) ; for ( ptr = head ; ptr != null ; ptr = ptr . next ) { um . put ( 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 . containsKey ( x / p_product ) && um . get ( x / p_product ) != ptr1 && um . get ( x / p_product ) != ptr2 ) { count ++ ; } } } return ( count / 3 ) ; } 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 ; } public static void main ( String [ ] args ) { 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 ; System . out . println ( " Count ▁ = ▁ " + countTriplets ( head , x ) ) ; } }