Linked List: Count triplets in a sorted DLL whose sum is equal to given value “k”.

Problem Statement:

You are given a Sorted DLL and a value ‘k’.

You need to get the triplets that the sum is equal to k

Example

Example: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 

k = 6

Output:
1

Solution

Method 1:

Use 3 loops and generate all triplets and check if it is equal to ‘k’.

Time Complexity : O(n3)

Method 2: Using of two pointers

Start traversing the DLL from left to right

For each current node, initialize two pointers “first = pointer_to_next_node to current”, “last = pointer to the last node”.

Now, we count pairs in the list from first to last that sum to the value.

Then we add count to the total_count of triplets.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;
  
struct Node 
{
    int data;
    struct Node* next;
    struct Node *prev;
};
 
int count_pairs(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 count_triplets(struct Node* head, int x)
{
    if (head == NULL)
        return 0;
 
    struct Node* current, *first, *last;
    int count = 0;
 
    // get the last node
    last = head;
    while (last->next != NULL)
        last = last->next;
 
    // traverse the DLL
    for (current = head; current != NULL; current = current->next) 
    {
 
        first = current->next;
 
        // count pairs with sum(x - current->data) in the range
        count += count_pairs(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 = 10;
 
    cout << "Count = "
         << count_triplets(head, x);
    return 0;
} 

Output:

Count = 1