yogeshhan
BAN USERWell this problem can be converted into binary representation
say we need k bits to represent the 1000 prisoners.
Now , we know that only one bottle is poisoned.
So represent 1000 bottles using binary numbers of length k.
Posion bottle X will be represented as sequence of k bits ...
and we use k soldiers
so if 000100101 first every bit represents a person set bits say that soldier drank it
so , there will such unique combination for poisoned bottle
depending on who died we can determine the bottle
in worst case takes O(lg 1000)
-Yogesh Hande
Well this problem can be converted into binary representation
say we need k bits to represent the 1000 prisoners.
Now , we know that only one bottle is poisoned.
So represent 1000 bottles using binary numbers of length k.
Posion bottle X will be represented as sequence of k bits ...
and we use k soldiers
so if 000100101 first every bit represents a person set bits say that soldier drank it
so , there will such unique combination for poisoned bottle
depending on who died we can determine the bottle
in worst case takes O(lg 1000)
-Yogesh Hande
Well this problem can be converted into binary representation
say we need k bits to represent the 1000 prisoners.
Now , we know that only one bottle is poisoned.
So represent 1000 bottles using binary numbers of length k.
Posion bottle X will be represented as sequence of k bits ...
and we use k soldiers
so if 000100101 first every bit represents a person set bits say that soldier drank it
so , there will such unique combination for poisoned bottle
depending on who died we can determine the bottle
in worst case takes O(lg 1000)
-Yogesh Hande
Well this problem can be converted into binary representation
say we need k bits to represent the 1000 prisoners.
Now , we know that only one bottle is poisoned.
So represent 1000 bottles using binary numbers of length k.
Posion bottle X will be represented as sequence of k bits ...
and we use k soldiers
so if 000100101 first every bit represents a person set bits say that soldier drank it
so , there will such unique combination for poisoned bottle
depending on who died we can determine the bottle
in worst case takes O(lg 1000)
-Yogesh Hande
Well this problem can be converted into binary representation
say we need k bits to represent the 1000 prisoners.
Now , we know that only one bottle is poisoned.
So represent 1000 bottles using binary numbers of length k.
Posion bottle X will be represented as sequence of k bits ...
and we use k soldiers
so if 000100101 first every bit represents a person set bits say that soldier drank it
so , there will such unique combination for poisoned bottle
depending on who died we can determine the bottle
in worst case takes O(lg 1000)
-Yogesh Hande
If both have similar length then you just increment heads of both one by one.
And the approach is , if you have an intersection node then the nodes after the intersection are common to both the lists.
So we just have to find the length of the list before the intersection node.
Please explain why this wont work
Consider two linked lists L1 and L2
1) Go through L1 and get its length l1
2) Go through L2 and get its length l2
3) Now find the difference d = l1-l2
4) So d is the number of nodes that are extra in longer list.
5) Traverse longer list till 'd' ..keep a pointer at this point
6) Now the length of longer list( That pointer) is equal to length of smaller list from front.
7) Now just traverse the the two list sequentially and compare every Node
Use merge sort.. count inversions when you put element from right array to left ..
- yogeshhan March 12, 2012