{"id":1358,"date":"2020-06-10T19:51:29","date_gmt":"2020-06-10T19:51:29","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1358"},"modified":"2022-06-17T05:34:36","modified_gmt":"2022-06-17T05:34:36","slug":"search-triplets","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/search-triplets\/","title":{"rendered":"Search Triplets"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Sorting<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

We have to find a triplet (n_{1}, n_{2}, n_{3})<\/code> in array such that sum of two number i.e. n_{1}+n_{2}<\/code> equals to the third number n_{3}<\/code>. We have to print the triplet in n_{3}<\/code> n_{1}<\/code> n_{2}<\/code> formation.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h4>\n
Input:\n1\n5\n20 40 30 50 70\n\nOutput:\n70 20 50\n\nExplanation:\nWe can see there are two such triplets (70,20,50) and (50,20,30). As the first triplet has a higher sum value, so we print 70 20 50.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach<\/strong>:<\/p>\n
\n
This problem can be solved if we form three loops for each number and check if the sum of two numbers is equal to the third number, we save all three numbers. Later all loops if no number is present in the array, we print -1. Else we print the largest of them. This approach takes O(n3<\/sup> ) which is not efficient, so we can solve this more efficiently by given approach.<\/p>\n<\/blockquote>\n
Efficient Approach<\/strong> :<\/p>\n
\n
1) We can find n_{2}<\/code> if we can subtract n_{1}<\/code> from n_{3}<\/code>, so we need to find only the pair n_{3}<\/code> and n_{1}<\/code>.
\n2) We can maintain a hash table which saves the presence of numbers in the array, hash table returns 1 if the number is present in the array, else returns 0.
\n3) We also know n_{3}<\/code> will be a larger number in the array, so we can sort the array so that we can iterate all larger numbers serial wise from the last index of the array.
\n4) So we now iterate from the last index of the sorted array, and find any element from smaller side of the array such that difference of both numbers exists in the array if any such pair exists we print the larger number, smaller number and their difference.<\/p>\n<\/blockquote>\n
Example<\/h3>\n
\n
Let array A<\/code> be,  <\/p>\n
\"\"<\/p>\n
Sorting array A<\/code> and maintaining a hash table H<\/code> which stores value 1 if index x<\/code> is present in array A<\/code>, else it stores 0.  <\/p>\n
Sorted Array A<\/code>,<\/p>\n
Hash Table H<\/code>,<\/p>\n
Required equation is : n_{1}+n_{2}=n_{3}<\/code><\/p>\n
For n_{3}, we iterate from last index of array MARKDOWN_HASH7fc56270e7a70fa81a5935b72eacbe29MARKDOWNHASH<\/code> as we need to print the largest value of n<\/em>{3}, Let the iterator be j=4<\/code>(last index)  <\/p>\n
For n_{1}, we ierate from start of array A<\/code>, Let the iterator be i=0<\/code>,<\/p>\n
    \n
  • \n
    For i=0, j=4<\/code> :
    \nA[i]<\/code> = 10, A[j]<\/code> = 70,
    \nWe check if A[j] - A[i]<\/code> is present in array or not, which can be verified from hash table H<\/code>,
    \nh[A[j] - A[i]]<\/code>
    \nh[70 - 10]<\/code>
    \nh[60]<\/code>
    \nAs h[60]<\/code> is 0, hence, this is not the required triplet, so we check next value of i i.e. i = 1<\/code>,<\/p>\n<\/li>\n
  • \n
    For i=1, j=4<\/code> :
    \nA[i]<\/code> = 20, A[j]<\/code> = 70,
    \nWe check if A[j] - A[i]<\/code> is present in array or not, which can be verified from hash table H<\/code>,
    \nh[A[j] – A[i]]`
    \nh[70 - 20]<\/code>
    \nh[50]<\/code>
    \nAs h[50]<\/code> is 1, hence, this is the required triplet, hence, we print the triplet in this form, i.e. A[i]<\/code> A[j]-A[i]<\/code> A[j]<\/code><\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
    Solutions<\/h3>\n
    \t\t\t\t\t\t