top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+3 votes
177 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 Google+ Share Button LinkedIn Share Button Multiple Social 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)

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

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...