{"id":4902,"date":"2021-09-14T11:17:28","date_gmt":"2021-09-14T11:17:28","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4902"},"modified":"2022-11-25T06:51:54","modified_gmt":"2022-11-25T06:51:54","slug":"count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/","title":{"rendered":"Count triplets in a sorted doubly linked list whose sum is equal to a given value X"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png\" alt=\"\" \/><\/p>\n<p>As we have already seen many articles on doubly linked lists, let\u2019s take another question in which we have to count triplets in a sorted doubly linked list whose sum is equal to a given value x, A doubly linked list contains an extra pointer called the previous pointer which stores the address of the previous node.<br \/>\nSo let us give a look at the problem statement of count triplets in a sorted doubly linked list whose sum is equal to a given value x.<\/p>\n<h2>How to count triplets in a sorted doubly linked list whose sum is equal to a given value x<\/h2>\n<p>Given a sorted doubly linked list of distinct nodes (No two nodes have the same data) and a value X. Count triplets in the list that sum to a given value X.<\/p>\n<p>Let\u2019s try to understand the problem statement with the help of some examples.<br \/>\nAccording to the problem statement, we are given a sorted doubly linked list and a value X. We have to count all the triplets from this doubly linked list which have a sum equal to X.<br \/>\nIf the doubly linked list is: head \u2192 2 \u2190\u2192 3 \u2190\u2192 5 \u2190\u2192 7 \u2190\u2192 10 \u2190\u2192 13 and X = 15.<\/p>\n<ul>\n<li>From the linked list, we can see that there are only two possible triplets (2, 3, 10) and (3, 5, 7), which have a sum equal to 15.  Rest all the possible triplets have a sum not equal to X.<\/li>\n<li>So our count of triplets will be 2.<\/li>\n<\/ul>\n<p>If the doubly linked list is: head \u2192 1 \u2190\u2192 2 \u2190\u2192 3 \u2190\u2192 4 \u2190\u2192 5 and X = 9.<\/p>\n<ul>\n<li>In this case, out of all the possible triplets, the triplets with the sum equal to 9 will be (1, 3, 5), (2, 3, 4).<\/li>\n<li>So our count of triplets will be 2.<\/li>\n<\/ul>\n<p><strong>Some more examples<\/strong><\/p>\n<pre><code>Sample Input 1 : head \u2192 1 \u2190\u2192 2 \u2190\u2192 3 \u2190\u2192 4,  X = 5\nSample Output 1: 0\n\nThere do not exist any triplet with sum equal to 5.\n\nSample Input 2: head \u2192 1 \u2190\u2192 3 \u2190\u2192 5 \u2190\u2192 7 \u2190\u2192 9 \u2190\u2192 11, X = 15\nSample Output 2: 3\n\nThe triplets are (1, 3, 11), (3, 5, 7), (1, 5, 9).<\/p><\/code><\/pre>\n<p>Now I think from the above examples, the problem statement is clear. So let&#8217;s see how we will approach it. Any Ideas?<\/p>\n<ul>\n<li>If not, it&#8217;s okay. We will see in the next section thoroughly how we can approach this problem.<\/li>\n<\/ul>\n<p><strong>Let\u2019s move to the approach section.<\/strong><\/p>\n<h2>Approach 1 of count triplets in a sorted doubly linked list whose sum is equal to a given value x<\/h2>\n<p>Our naive approach will be to traverse the linked list using three nested loops, and while traversing, for every triplet, we will check whether the triplet sums up to X  or not:<\/p>\n<ul>\n<li>If it does sum up to X, then count this triplet combination.<\/li>\n<li>Else continue with the loops.<\/li>\n<\/ul>\n<p><strong>Time complexity of count triplets in a sorted doubly linked list whose sum is equal to a given value x :<\/strong> O(N<sup>3<\/sup>), Since we are using three nested loops to count triplet combinations.<\/p>\n<p><strong>Space complexity of count triplets in a sorted doubly linked list whose sum is equal to a given value x :<\/strong> O(1), As no extra space is used.<\/p>\n<p>Next, we will see how we can reduce this complexity. Any ideas?<\/p>\n<ul>\n<li>If not, it&#8217;s okay. We will see in the next section how we can reduce the time complexity.<\/li>\n<\/ul>\n<p>Let\u2019s move to a comparatively better approach than approach 1.<\/p>\n<h2>Approach 2 of count triplets in a sorted doubly linked list whose sum is equal to a given value x<\/h2>\n<p>The idea is to create a hashmap with (key, value) pair to store the node\u2019s data as the key and a pointer to that node as the value.<\/p>\n<p>Now, generate each possible pair of nodes from the linked list. For each pair of nodes, calculate the <strong>pair_sum<\/strong>(sum of data in the two nodes) and check whether <strong>(X-pair_sum)<\/strong> exists in the hash table or not.<\/p>\n<ul>\n<li>\n<p>If it exists, then also verify that the two nodes in the pair are not the same as the node associated with <strong>(X-pair_sum)<\/strong> in the hash table and finally increment the count.<\/p>\n<\/li>\n<li>\n<p>Finally, we will be returning <strong>(count \/ 3)<\/strong> as our output as each of our triplets having sum equal to x has been counted 3 times during the above process.<\/p>\n<\/li>\n<\/ul>\n<h2>Algorithm 2 of count triplets in a sorted doubly linked list whose sum is equal to a given value x<\/h2>\n<ul>\n<li>Initialize the <strong>count<\/strong> to zero.<\/li>\n<li>Now traverse through the linked list and store the node\u2019s data as a key and a pointer to that node as the value in a map.<\/li>\n<li>\n<p>Further, iterate over the linked list using two nested loops in which the first loop iterates from head to NULL using ptr1, and the second nested loop iterates from the next node of pointer of first loop <strong>(ptr1-&gt;next)<\/strong> to NULL.<\/p>\n<ul>\n<li>Now in the variable <strong>pair_sum<\/strong>, stores the sum of data of two pointers, i.e., <strong>ptr1-&gt;data + ptr2-&gt;data<\/strong>.<\/li>\n<li>Now check if the map contains <strong>(X &#8211; pair_sum)<\/strong> and also check if the two nodes in the pair are not the same as the node associated with a value <strong>(X-pair_sum)<\/strong> in the map.<\/li>\n<li>Now, if the condition satisfies, increment the <strong>count<\/strong>.<\/li>\n<\/ul>\n<\/li>\n<li>Finally, we have to return <strong>(count \/ 3)<\/strong> as our output because each triplet has been counted 3 times during the above process.<\/li>\n<\/ul>\n<p><strong>Time Complexity count triplets in a sorted doubly linked list whose sum is equal to a given value x:<\/strong> O(N<sup>2<\/sup>), Since we have traversed through the linked list twice for every Element.<\/p>\n<p><strong>Space Complexity of count triplets in a sorted doubly linked list whose sum is equal to a given value :<\/strong> O(N), No extra space used.<\/p>\n<p>Now we can see that this approach is far better than the previous approach, but we are also using extra space here. So next, we will try to see if we can somehow reduce the space complexity. Any Ideas?<\/p>\n<ul>\n<li>If not, it&#8217;s okay. We will see in the next approach how we can do this in less space complexity.<\/li>\n<\/ul>\n<p>Let&#8217;s move to the next approach.<\/p>\n<h2>Approach 3 of count triplets in a sorted doubly linked list whose sum is equal to a given value x<\/h2>\n<p>This approach is an efficient one. Here the idea is to traverse the linked list from left to right, and for each node, count number of pairs in the list that sum up to the value <strong>(X &#8211; Current Node\u2019s Data)<\/strong>.<\/p>\n<p>Let&#8217;s see the algorithm.<\/p>\n<h2>Algorithm 3 of count triplets in a sorted doubly linked list whose sum is equal to a given value x<\/h2>\n<ul>\n<li>\n<p>Create a <strong>count<\/strong> named variable and initialize it to 0. This <strong>count<\/strong> variable will keep track of the total number of possible triplets in the linked list having sum X.<\/p>\n<\/li>\n<li>\n<p>Start traversing the linked list from the head node using a pointer variable <strong>curr<\/strong>. <\/p>\n<\/li>\n<li>\n<p>During traversal for each node, initialize two pointers <strong>begin<\/strong> and <strong>end<\/strong> to next of current node <strong>(curr-&gt;next)<\/strong> and end node of linked list respectively.<\/p>\n<\/li>\n<li>\n<p>Count the number of pairs in list from <strong>begin<\/strong> to <strong>end<\/strong> having sum equal to <strong>(X &#8211; curr\u2192data)<\/strong>. Add the count of pairs to the variable <strong>count<\/strong>. Please visit the following article to see how we can find the pairs in a doubly linked list having a certain sum <a href=\"https:\/\/prepbytes.com\/blog\/linked-list\/find-pairs-with-given-sum-in-sorted-doubly-linked-list\/\">Check out this article<\/a>.<\/p>\n<\/li>\n<li>\n<p>Finally, after the traversal is over, the <strong>count<\/strong> variable will have the count of all possible triplets having sum equal to X.<\/p>\n<\/li>\n<\/ul>\n<h3>Dry Run of count triplets in a sorted doubly linked list whose sum is equal to a given value x <\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_1.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_2.png\" alt=\"\" \/><\/p>\n<h2>Code Implementation of count triplets in a sorted doubly linked list whose sum is equal to a given value x<\/h2>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_4904 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_4904 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_4904 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_4904 .wpsm_nav-tabs > li.active > a, #tab_container_4904 .wpsm_nav-tabs > li.active > a:hover, #tab_container_4904 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_4904 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_4904 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_4904 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_4904 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_4904 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_4904 .wpsm_nav-tabs > li > a:hover , #tab_container_4904 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_4904 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_4904 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_4904 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_4904 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_4904 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_4904 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_4904 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_4904 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_4904 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_4904 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_4904 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_4904\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_4904\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_4904_1\" aria-controls=\"tabs_desc_4904_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_4904\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_4904_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include <bits\/stdc++.h>\r\nusing namespace std;\r\n\r\n\/* Node structure of the doubly linked-list*\/\r\nstruct Node {\r\n    int data;\r\n    struct Node* next, *prev;\r\n};\r\n\r\n\/* Using this function we will count the number of pairs having sum equal to given the given value *\/\r\nint countValpairs(struct Node* begin, struct Node* end, int value)\r\n{\r\n    int count = 0;\r\n    while (begin != NULL && end != NULL && begin != end && end->next != begin) {\r\n        \r\n        if ((begin->data + end->data) == value) {\r\n            count++;\r\n            begin = begin->next;\r\n            end = end->prev;\r\n        }\r\n        \r\n        else if ((begin->data + end->data) > value){\r\n            end = end->prev;\r\n        }\r\n        \r\n        else{\r\n            begin = begin->next;\r\n        }\r\n    }\r\n    return count;\r\n}\r\n\r\n\/* Using this function we will count the number of triplets in a list having sum equal to X *\/\r\nint countXtriplets(struct Node* head, int X)\r\n{\r\n    if (head == NULL){\r\n        return 0;\r\n    }\r\n    struct Node* current, *first, *last;\r\n    int count = 0;\r\n    \r\n    last = head;\r\n    while (last->next != NULL){\r\n        last = last->next;\r\n    }\r\n    \r\n    for (current = head; current != NULL; current = current->next) {\r\n        first = current->next;\r\n        count += countValpairs(first, last, X - current->data);\r\n    }\r\n\r\n    return count;\r\n}\r\n\r\n\/* Using this function we will add a new node at the beginning of doubly linked list *\/\r\nvoid insertAtHead(struct Node** head, int data)\r\n{\r\n    struct Node* temp = new Node();\r\n    temp->data = data;\r\n    temp->next = temp->prev = NULL;\r\n    \r\n    if ((*head) == NULL){\r\n        (*head) = temp;\r\n\r\n    }else{\r\n\r\n        temp->next = *head;\r\n        (*head)->prev = temp;\r\n        (*head) = temp;\r\n    }\r\n}\r\n\r\nint main()\r\n{\r\n    struct Node* head = NULL;\r\n    insertAtHead(&head, 5);\r\n    insertAtHead(&head, 4);\r\n    insertAtHead(&head, 3);\r\n    insertAtHead(&head, 2);\r\n    insertAtHead(&head, 1);\r\n    \r\n    int X = 9;\r\n    \r\n    cout << \"Count of triplets having sum equal to \"<<X<<\" is \"<< countXtriplets(head, X);\r\n    \r\n    return 0;\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_4904 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_4904 a\"),jQuery(\"#tab-content_4904\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<pre><code>Output\nCount of triplets having sum equal to 9 is 2<\/code><\/pre>\n<p><strong>Time Complexity:<\/strong> O(N<sup>2<\/sup>), Since we have traversed through the linked list twice for every element.<\/p>\n<p>So, In this blog, we have learned How to count triplets in a sorted doubly linked list whose sum is equal to a given value x. If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Linked List<\/a>.<\/p>\n<h2>FAQs<\/h2>\n<p><strong>1. What are the types of a linked lists?<\/strong><br \/>\nThe linked lists are of 4 types:<\/p>\n<ul>\n<li>Singly-linked lists<\/li>\n<li>Doubly linked lists<\/li>\n<li>Circular linked lists<\/li>\n<li>Circular doubly linked lists<\/li>\n<\/ul>\n<p><strong>2. What is a triplet?<\/strong><br \/>\nA triplet is a tuple of three different elements from other indexes for example i, j, k.<\/p>\n<p><strong>3. What is an ordered list?<\/strong><br \/>\nThe ordered list is a collection of items in which the order of the items matters.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>As we have already seen many articles on doubly linked lists, let\u2019s take another question in which we have to count triplets in a sorted doubly linked list whose sum is equal to a given value x, A doubly linked list contains an extra pointer called the previous pointer which stores the address of the [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[125],"tags":[],"class_list":["post-4902","post","type-post","status-publish","format-standard","hentry","category-linked-list"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Count triplets in a sorted doubly linked list whose sum is equal to a given value X<\/title>\n<meta name=\"description\" content=\"Count triplets in a sorted doubly linked list whose sum is equal to a given value X. This blog explains how to count triplets in a sorted doubly linked list whose sum is equal to a given value x.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Count triplets in a sorted doubly linked list whose sum is equal to a given value X\" \/>\n<meta property=\"og:description\" content=\"Count triplets in a sorted doubly linked list whose sum is equal to a given value X. This blog explains how to count triplets in a sorted doubly linked list whose sum is equal to a given value x.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-09-14T11:17:28+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-11-25T06:51:54+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png\" \/>\n<meta name=\"author\" content=\"PrepBytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"PrepBytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"7 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/\"},\"author\":{\"name\":\"PrepBytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\"},\"headline\":\"Count triplets in a sorted doubly linked list whose sum is equal to a given value X\",\"datePublished\":\"2021-09-14T11:17:28+00:00\",\"dateModified\":\"2022-11-25T06:51:54+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/\"},\"wordCount\":1372,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/\",\"name\":\"Count triplets in a sorted doubly linked list whose sum is equal to a given value X\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png\",\"datePublished\":\"2021-09-14T11:17:28+00:00\",\"dateModified\":\"2022-11-25T06:51:54+00:00\",\"description\":\"Count triplets in a sorted doubly linked list whose sum is equal to a given value X. This blog explains how to count triplets in a sorted doubly linked list whose sum is equal to a given value x.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Linked list articles\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/linked-list\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Count triplets in a sorted doubly linked list whose sum is equal to a given value X\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\",\"name\":\"PrepBytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"caption\":\"PrepBytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Count triplets in a sorted doubly linked list whose sum is equal to a given value X","description":"Count triplets in a sorted doubly linked list whose sum is equal to a given value X. This blog explains how to count triplets in a sorted doubly linked list whose sum is equal to a given value x.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/","og_locale":"en_US","og_type":"article","og_title":"Count triplets in a sorted doubly linked list whose sum is equal to a given value X","og_description":"Count triplets in a sorted doubly linked list whose sum is equal to a given value X. This blog explains how to count triplets in a sorted doubly linked list whose sum is equal to a given value x.","og_url":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-09-14T11:17:28+00:00","article_modified_time":"2022-11-25T06:51:54+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png","type":"","width":"","height":""}],"author":"PrepBytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"PrepBytes","Est. reading time":"7 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/"},"author":{"name":"PrepBytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e"},"headline":"Count triplets in a sorted doubly linked list whose sum is equal to a given value X","datePublished":"2021-09-14T11:17:28+00:00","dateModified":"2022-11-25T06:51:54+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/"},"wordCount":1372,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/","url":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/","name":"Count triplets in a sorted doubly linked list whose sum is equal to a given value X","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png","datePublished":"2021-09-14T11:17:28+00:00","dateModified":"2022-11-25T06:51:54+00:00","description":"Count triplets in a sorted doubly linked list whose sum is equal to a given value X. This blog explains how to count triplets in a sorted doubly linked list whose sum is equal to a given value x.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000780126-Article_138.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/count-triplets-in-a-sorted-doubly-linked-list-whose-sum-is-equal-to-a-given-value-x\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Linked list articles","item":"https:\/\/prepbytes.com\/blog\/category\/linked-list\/"},{"@type":"ListItem","position":3,"name":"Count triplets in a sorted doubly linked list whose sum is equal to a given value X"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e","name":"PrepBytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","caption":"PrepBytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4902","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=4902"}],"version-history":[{"count":8,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4902\/revisions"}],"predecessor-version":[{"id":10762,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4902\/revisions\/10762"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=4902"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=4902"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=4902"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}