top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+3 votes
399 views
Find a triplet from three linked lists with sum equal to a given number??
posted Apr 11, 2014 by Atul Mishra

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

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 Prakash
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

...