Problem Details
Count triplets in a sorted doubly linked list whose sum is equal to a given value x
Last Updated: 25 Dec, 2020
Count triplets in a sorted doubly linked list whose sum is equal to a given value x
Moderate
Asked in companies
You are given a sorted doubly linked list of distinct nodes that means no two nodes present in the list have the same data. You are also given an integer 'X'.Your task is to count the number of triplets in the list that sum up to a given value 'X'.
A doubly linked List (DLL) contains an extra pointer, called the previous pointer, together with the next pointer and data, which are there in the singly linked list such that both forward and backward navigation is possible.
For example, DLL is 1<->2<->3<->4 NULL and the given integer 'X' is 9, then the number of triplets having the sum 9 is only one, and that is (2,3,4).
Note:
1. If no such triplets exist, return zero.
2. At least three elements will always be present in the linked list.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.
The first line of each test case contains space-separated integers denoting the nodes of the linked list. Each line is guaranteed to have -1 at the end to signify the end of the linked list.
The second line of each test case contains a single integer 'X' denoting the value of triplet sum.
Output format :
For each test case, print an integer denoting the count of the triplets.
The output of every test case will be printed in a separate line.
Note:
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= 'T' <= 10
3 <= 'N' <= 100
1 <= 'X' <= 10^8
1 <= 'V' <= 10^8
Where 'V' denotes any linked list element.
Time Limit: 1 sec
Approaches
The idea is to traverse the linked list using three nested loops,
Such each possible combination is tried and checked whether it sums up to the value X and, if it does, increment the counter for the result.
Steps:
- Initialize the COUNT to zero.
- For the first loop, initialize the pointer PTR1 to the head of the given linked list, HEAD.
- For the next nested loop, we initialize the pointer PTR2 to the next loop pointer, i.e., PTR1NEXT. Similarly, in the third loop, we initialize pointer PTR3 to next of the second loop pointer, i.e., PTR2.
- And for each iteration in the last loop, check whether elements in the triplet sum up to X or not.
- If the sum corresponds to X i.e. if((PTR1.DATA + PTR2.DATA+PTR3.DATA) equals X), increase the COUNT.
- Else do nothing and move forward to the next iteration.
The idea is to create a hashmap with (key, value) pair in which the key will be the DLLNODE.DATA and value will be a pointer to that node, further traverse the doubly linked list and store each node’s data and its pointer pair in the hash map and check whether (X-PAIRSUM) exists in the hash map or not and If it exists, then also verify that the two nodes in the pair are not same to the node associated with (X-PAIRSUM) in the hash table. Finally, return COUNT/3 as the answer.
Steps:
- Initialize the COUNT to zero.
- Now initialize the hashmap as ‘MAP,’ which stores the key as a NODE.DATA and value as a pointer to that node.
- Now insert the pair in hashmap by iterating the loop from head to null.
- Further, iterate two nested loops in which the first loop iterates to head to null and the second nested loop iterates from pointer to next to null.
- Now store the PAIRSUM, which stores the sum of data of two pointers, i.e., PTR1.DATA + PTR2.DATA.
- Now check if ‘MAP’ contains X - PAIRSUM and check if the two nodes in the pair are not the same as the node associated with (X-PAIRSUM) in the hashmap.
- Now, if the condition satisfies, increment the COUNT.
- Finally, return COUNT/3 as each triplet is counted 3 times in the above process.
The idea is to have two pointers in which we iterate through the linked list, checking each value in the COUNTPAIRS function. A COUNTPAIRS function counts the number of pairs whose sum is equal to the given value and then traverse the doubly linked list from left to right.
Steps:
- Make a COUNTPAIRS function.
- Initialize the COUNT to zero.
- Now inside the COUNTPAIRS run a loop which terminates when either of two pointers become null, or they cross each other, i.e., SECOND.NEXT == FIRST, or they become the same (FIRST == SECOND).
- Now inside the loop, check for pair, i.e., FIRST.DATA + SECOND.DATA equals VALUE, and if it satisfies, increment the COUNT by one.
- Now increment the pointer FIRST to forward direction FIRST = FIRST.NEXT and SECOND in backward direction SECOND = SECOND.PREV.
- Else if FIRST.DATA + SECOND.DATA is greater than VALUE do SECOND = SECOND.PREV.
- Else do FIRST = FIRST.NEXT
- Return COUNT for this function
- Now for the main function COUNTTRIPLETS initialize the COUNT variable for this function to zero.
- Now get the LAST pointer to the last node of the doubly linked list.
- For each current node during the traversal, initialize two pointers: FIRST, that points to the node next to the current node, i.e., CURRENT.NEXT and LAST, that points to the last node of the list
- Now, call the COUNTPAIRS function in the list from first to the last pointer that sums up the value of X – current node’s data.
- Add this count to the total number of counts of the triplets.
- Loop termination conditions are also different from arrays in the count pair function. The loop terminates when either of two pointers become NULL, or they cross each other (last->next = first), or they become the same (first == last) in the COUNTPAIRS function.