Thursday, 23 April 2015

Given 3 linked list , find a triplet such that there's sum equals a given number


    A function to check if there exist a triplet in three given linked list such that the tripplet's sum is equal to a given number
    Let there be 3 linked list a , b , c .
   
    1 Sort list b in ascendinng and c and descending order respectively

    2 For each node in  list a ,check if there exist a triplet traversing list b and c as shown in function below.

    The technique is called Quadratic algorithm for 3 sum problem

    Function assumes list b and c already satisfies 1st step and all list are of same length


#include<iostream>
using namespace std;
struct node {
    int data;
    struct node * next;


};

bool isTripletPresent(struct node* aHead, struct node* bHead,  struct node* cHead, int num)
{
    struct node* a = aHead;
    while (a != NULL)
    {
        struct node* b = bHead;
        struct node* c = cHead;

        while (b != NULL  && c != NULL)
        {
            int sum = a->data + b->data + c->data;
            if (sum == num)
            {
                cout << "Found";
                return true;
            }
            else if (sum < num)
            {
                //look for greater value in b
                b = b->next;
            }
            else {
                //look for smaller value in c
                c = c->next;
            }


                       
        }

        a = a->next;



    }
    cout << "No such triplet ";
    return false;
}

No comments:

Post a Comment