Hi...
Sorry to ask the help regarding the same old problem. I am not
good at algorithms. I saw this problem in older posts. An O(nlogn)
solution is given there. But Im not able to understand the solution.
In the Onlogn solution given there how did he make sure that the two
sets are divided into two equal parts n/2.
The solution given there is
The solution is straight away with the hint.
Pick one nut compare all the other bolts. You could get one matching
bolt
and all the other bolts will be smaller or bigger.
Split the smaller bolts into an array and the bigger bolts into another
array.
Now based on the bolt which matches with the nut you used for
comparsion.
Similarly based on that bolt split the nuts into two arrays.
Apply this thing recursively.
This thing has complexity
T(n) = T(n/2) + T(n/2) + 2n
hence O(n log n)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
