Find 0 sum elements in three Linked lists
Given three lists: A, B and C of length n each. Write a function which returns true if any 3 three numbers (1 from each list), sum up to zero. Else return false, if there is no such combination.
Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
const char * (node*p,node *q,node *r){
ReplyDeletewhile(p!=null){
while(q!=null){
int d=p->value+q->value;
while(r!=null){
if(-d==r->value)
return "true";
else
r=r->next;
}
q=q->next;
}
p=p->next;
}
return "false";
}
Time Complexity O(n^3) for your solution.
ReplyDeleteHere is another thought
Make a Hash Map for sum of all the elements of first two Linked Lists. Now traverse the third list, for each element M (of third list), look for -M in Hash Map, if found return true.
i hv very less idea about the hash map. can you please elaborate the method?
ReplyDeletewhile(p!=null){
ReplyDeletewhile(q!=null){
int d=p->value+q->value;
By doing this you are computing sum of all pairs of two linked list.this is done in o(n^2).
You add these elements in a hash map which takes o(1) time.
Now traverse through the third linked list and for every element search for collision which again will take constant time.
so whole algo will take o(n^2) time.
for hashing you can look at wikipedia.
ReplyDeletelet's take a brief intro how insertion and lookup takes o(1) time.
Basically, a hash table is an array containing all of the keys to search on. The position of each key in the array is determined by the hash function, which can be any function which always maps the same input to the same output. We shall assume that the hash function is O(1).
So when we insert something into the hash table, we use the hash function (let's call it h) to find the location where to put it, and put it there. Now we insert another thing, hashing and storing. And another. Each time we insert data, it takes O(1) time to insert it (since the hash function is O(1).
Looking up data is the same. If we want to find a value, x, we have only to find out h(x), which tells us where x is located in the hash table. So we can look up any hash value in O(1) as well.
Thanks for all your efforts...really helpful.
ReplyDeletethnx buddy..:)
ReplyDelete