Count triplets in a sorted doubly linked list whose sum is equal to a given value x | C ++ implementation to count triplets in a sorted doubly linked list whose sum is equal to a given value ' x ' ; structure of node of doubly linked list ; function to count pairs whose sum equal to given ' value ' ; The loop terminates when either of two pointers become NULL , or they cross each other ( second -> next == first ) , or they become same ( first == second ) ; pair found ; increment count ; move first in forward direction ; move second in backward direction ; if sum is greater than ' value ' move second in backward direction ; else move first in forward direction ; required count of pairs ; function to count triplets in a sorted doubly linked list whose sum is equal to a given value ' x ' ; if list is empty ; get pointer to the last node of the doubly linked list ; traversing the doubly linked list ; for each current node ; count pairs with sum ( x - current -> data ) in the range first to last and add it to the ' count ' of triplets ; required count of triplets ; 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 ; 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 countPairs ( struct Node * first , struct Node * second , int value ) { int count = 0 ; while ( first != NULL && second != NULL && first != second && second -> next != first ) { if ( ( first -> data + second -> data ) == value ) { count ++ ; first = first -> next ; second = second -> prev ; } else if ( ( first -> data + second -> data ) > value ) second = second -> prev ; else first = first -> next ; } return count ; } int countTriplets ( struct Node * head , int x ) { if ( head == NULL ) return 0 ; struct Node * current , * first , * last ; int count = 0 ; last = head ; while ( last -> next != NULL ) last = last -> next ; for ( current = head ; current != NULL ; current = current -> next ) { first = current -> next ; count += countPairs ( first , last , x - current -> data ) ; } return count ; } 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 = 17 ; cout << " Count ▁ = ▁ " << countTriplets ( head , x ) ; return 0 ; }