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