   # Find a triplet from three linked lists with sum equal to a given number??

+3 votes
181 views
Find a triplet from three linked lists with sum equal to a given number?? posted Apr 11, 2014
Share this question

## 1 Answer

+1 vote

One Possible Solution:----O(n^2)
We have to find a + b + c = SUM where a from first list , b from second list, c from third list

Sort the first Link List in increasing order and second in decreasing order using Merge sort

``````tmp=thirdList->start
while ( tmp != NULL ) {
c = tmp->data
toFind=SUM  - c
t1=firstList->start
t2=secondList->start
while (  t1 != NULL && t2 != NULL){
a= t1->data, b= t2->data
if( a + b < toFind  )
t1=t1->next
else if (a + b > toFind)
t2=t2->next
else{                                                            //  a + b ==toFind
printf ( " %d %d %d ", a ,b ,c  )         // the triplets found
return
}
}
tmp=tmp->next
}
print (" Not Found")
``````

Time Complexity-
Assumption- N- length of First list, M- length of second list, L-length of third list
O(NlogN) + O(MlogM) + O( L * ( M + N)) = O(n^2) answer Apr 17, 2014 by
Similar Questions
+1 vote

Say you are given

``````int a[ ] = {1,2,3,4};
int b[ ] = {4,3,2,1};
int S = 5;
``````

Now the task is to find all pairs of two number which adds up to S (One number from a and other number from b).

+7 votes

You have a 2D matrix. Only two ZEROs in matrix.
Find the path from 1st zero to 2nd zero with least sum.

``````1       6       8       9       0       3

4       9       -5      5       11      13

8       9       44      23      15      -20

7       9       7       -13     14      11

0       16      23      31      16      7

67      5       4       23      21      19
``````

Answer

``````1       6       8       9       0  ----> 3
|
4       9       -5      5       11      13
|
8       9       44      23      15      -20
|
7 <---- 9 <---- 7 <--- -13 <--- 14 <---  11
|
0       16      23      31      16        7

67      5       4       23      21       19
``````
0 votes

Suppose A is represented by 1, B by 2 ...and Z by 26.

Now we are given a number, and we need to find number of possible decoding for this number. No need to consider number starts with zero.

Example:
Input – 1234,
Output – 3(ABCD, AWD, LCD)

+7 votes

Input:
First List: 5->6->3 // represents number 563
Second List: 8->4->2 // represents number 842
Output
Resultant list: 4->7->4->0->4->6 // represents number 474046