{"id":2686,"date":"2021-10-14T12:20:00","date_gmt":"2021-10-14T06:50:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2686"},"modified":"2022-03-15T02:33:16","modified_gmt":"2022-03-14T21:03:16","slug":"count-the-triplets","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/count-the-triplets\/","title":{"rendered":"Count The Triplets Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#basic-approach\">Basic Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#-java-implementation\"><meta charset=\"utf-8\">Java Implementation<\/a><\/li><li><a href=\"#-python-implementation\"><meta charset=\"utf-8\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#efficient-approach-using-hashing\">Efficient Approach (Using Hashing)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-hashing-method\">C++ Code For Hashing Method<\/a><\/li><li><a href=\"#-java-code-for-hashing-method\"><meta charset=\"utf-8\">Java Code For Hashing Method<\/a><\/li><li><a href=\"#-python-code-for-hashing-method\"><meta charset=\"utf-8\">Python Code For Hashing Method<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given an array <strong>A[]<\/strong> consisting of <strong>N<\/strong> integers. The task is to count the number of triples (A[i], A[j], A[k]), where <strong>i<\/strong>, <strong>j, <\/strong>and <strong>k<\/strong> denote the respective indices, such that one of the integers can be written as the summation of the other two integers.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input:&nbsp; <\/strong>A[] = {1, 2, 3, 4, 5}<br><strong>Output: <\/strong>4<br><strong>Explanation:<\/strong><br>The valid triplets are &#8211;<\/p>\n\n\n\n<ul><li>(1, 2, 3) : 1 + 2 = 3<\/li><li>(2, 3, 5) : 2 + 3 = 5<\/li><li>(1, 3, 4) : 1 + 3 = 4<\/li><li>(1, 4, 5) : 1 + 4 = 5<\/li><\/ul>\n\n\n\n<p><strong>Input: <\/strong>A[] = {2, 3, 6,9}<br><strong>Output:<\/strong> 1<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"basic-approach\">Basic Approach<\/h2>\n\n\n\n<p>The most basic approach is to run three nested loops from <strong>1<\/strong> till <strong>N<\/strong> and check if the summation of any two integers equals the third integer.<\/p>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: 700px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/9ec61b31d6a97fd972a5 title='Interviewbit Ide snippet\/9ec61b31d6a97fd972a5' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"-java-implementation\"><span id=\"java-implementation\"><meta charset=\"utf-8\">Java Implementation<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: 700px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/6fc9d000ca1ff31c1676 title='Interviewbit Ide snippet\/6fc9d000ca1ff31c1676' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"-python-implementation\"><span id=\"python-implementation\"><meta charset=\"utf-8\">Python Implementation<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: 700px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/ffd9373a15e73facb62d title='Interviewbit Ide snippet\/ffd9373a15e73facb62d' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N^3) where N is the number of nodes of the binary tree<strong>.Space Complexity:<\/strong> O(1)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"efficient-approach-using-hashing\">Efficient Approach (Using Hashing)<\/h2>\n\n\n\n<p>The approach is to calculate all possible combinations such that the summation of any two integers is equal to the third integers. If we observe carefully, there can only be 4 possible cases, which satisfy the above condition.<\/p>\n\n\n\n<ul><li><strong>(0, 0, 0)<\/strong> :<strong> <\/strong>As 0 + 0 = 0, it is a valid triplet. Therefore, the total possible ways = freq[0]C3, as among all possible frequencies of 0, we just need to consider triplets.<\/li><li><strong>(0, x, x) <\/strong>:<strong> <\/strong>As 0 + x = x, it is a valid triplet. Therefore, the total possible ways = freq[x]C2 * freq[0]C1, as among all possible frequencies of <strong>0<\/strong> and <strong>x<\/strong>, we just need to consider the triplet containing one 0 and two <strong>x<\/strong>.<\/li><li><strong>(x, x, 2x) : <\/strong>As x + x = 2x, it is a valid triplet. Therefore, the total possible ways = freq[x]C2 * freq[2x]C1, as among all possible frequencies of <strong>x<\/strong> and <strong>2x<\/strong>, we just need to consider the triplet containing one <strong>2x<\/strong> and one <strong>x<\/strong>.<\/li><li><strong>(x, y, x + y) : <\/strong>The total possible ways = freq[x]C1 * freq[y]C1 * freq[x + y]C1, as among all possible frequencies of <strong>x<\/strong>, <strong>y<\/strong> and <strong>x + y<\/strong>, we just need to consider the triplet containing all <strong>x<\/strong>, <strong>y<\/strong> and <strong>x + y<\/strong>.<\/li><\/ul>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"620\"  height=\"245\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Count the Triplets Image2\"  class=\"wp-image-2788 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 620px) 100vw, 620px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image2.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image2.png 620w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image2-300x119.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image2-380x150.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image2-550x217.png 550w\" ><\/figure><\/div>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-2787 pk-lazyload\"  width=\"594\"  height=\"261\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 594px) 100vw, 594px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image1.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image1.png 696w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image1-300x132.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image1-380x167.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image1-550x242.png 550w\" ><\/figure><\/div>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"545\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-2789 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image3.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image3.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image3-300x160.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image3-768x409.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image3-380x202.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image3-550x293.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Count-the-Triplets-Image3-800x426.png 800w\" ><\/figure><\/div>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Compute the value of the <strong>maximum element, mx <\/strong>of the array.<\/li><li>Build a frequency array, <strong>freq<\/strong> of size <strong>mx + 1<\/strong> and store the frequency of all the elements of the array <strong>A[]<\/strong>.<\/li><li>Initialise a <strong>count<\/strong> variable<strong> <\/strong>and consider the above four cases one by one:<ul><li>If the triplet is <strong>(0, 0, 0)<\/strong>, add freq[0]C3 to <strong>count<\/strong>.<\/li><li>If the triplet is <strong>(0, x, x)<\/strong>, add freq[0]C1 * freq[x]C2 to <strong>count<\/strong>.<\/li><li>If the triplet is <strong>(x, x, 2x)<\/strong>, add freq[x]C2 * freq[2x]C1 to <strong>count<\/strong>.<\/li><li>If the triplet is <strong>(x, y, x + y)<\/strong>, add freq[x]C1 * freq[y]C1 * freq[x + y]C1 to <strong>count<\/strong>.<\/li><\/ul><\/li><li>Return <strong>count<\/strong>.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-for-hashing-method\">C++ Code For Hashing Method<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: 700px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/595b041e9d491790f668 title='Interviewbit Ide snippet\/595b041e9d491790f668' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"-java-code-for-hashing-method\"><span id=\"java-code-for-hashing-method\"><meta charset=\"utf-8\">Java Code For Hashing Method<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: 700px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/af5e8c25e4bd09abe629 title='Interviewbit Ide snippet\/af5e8c25e4bd09abe629' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"-python-code-for-hashing-method\"><span id=\"python-code-for-hashing-method\"><meta charset=\"utf-8\">Python Code For Hashing Method<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: 700px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/110718c6b360a35c8328 title='Interviewbit Ide snippet\/110718c6b360a35c8328' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N^2) where N is the number of nodes of the binary tree<strong>.<\/strong> <br><strong>Space Complexity:<\/strong> O(N), as a map is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/maximum-sum-triplet\/\" target=\"_blank\">Maximum Sum Triplets<\/a><br><a href=\"https:\/\/www.interviewbit.com\/problems\/3-sum-zero\/\" target=\"_blank\" rel=\"noreferrer noopener\">3 Sum Zero<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>How do you count triplets in an array?<br><\/strong>The triplets can be counted by running three nested loops over the size of the array.<br><\/p>\n\n\n\n<p><strong>What are triplets in an array?<br><\/strong>The triplet of an array is a tuple of three elements of different indices, represented by (<strong>i, j, k).<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an array A[] consisting of N integers. The task is to count the number of&hellip;\n","protected":false},"author":5,"featured_media":2790,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[463,464],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2686"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2686"}],"version-history":[{"count":9,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2686\/revisions"}],"predecessor-version":[{"id":7769,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2686\/revisions\/7769"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2790"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2686"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2686"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2686"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}