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

178 views
Find a triplet from three linked lists with sum equal to a given number??
posted Apr 11, 2014

+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
}
``````

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).

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

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

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)

+1 vote

Alex has been asked by his teacher to do an assignment on sums of digits of a number. The assignment requires Alex to find the sum of sums of digits of a given number, as per the method mentioned below.
If the given number is 582109, the Sum of Sums of Digits will be calculated as =
= (5 + 8 + 2 + 1 + 0 + 9) + (8 + 2 + 1 + 0 + 9) + (2 + 1 + 0 + 9) + (1 + 0 + 9) + (0 + 9) + (9)
= 25 + 20 + 12 + 10 + 9 + 9 = 85

Alex contacts you to help him write a program for finding the Sum of Sums of Digits for any given number, using the above method.

Help Alex by completing the login in the given function sumOfSumsOfDigits which takes as input an integer input1 representing the given number.
The function is expected to return the "Sum of Sums of Digits" of input1.

Assumptions: For this assignment, let us assume that the given number will always contain more than 1 digit, i.e. the given number will always be >9.