You have m nuts and n bolts, Every unique nut is fit in every unique bolt, Suggest an effective algorithm for placing each nut in each bolt in less no. of passes? Click for Solution |
-
Warning: Illegal string offset 'name' in /home/prepdo6/gpl4you/discussquessub.php on line 681
A sort the nuts and bolts list in order of ascending size in O(mlog(m)) and O(nlog(n)) times den one by one pick a nut from the sorted array and fit it into the bolts this process will take O(n) time so total time taken is O(nlog(n)) by the algo
Explore
- GPL4you
- Home
- Prepdoor - Online Mock Test
- About
- FAQs
- Contact
- Contact Us
© 2011 - gpl4you | All Rights Reserved.
O(N). This constant can be improved.
Here is the algorithm:
1) Sort all nuts OR bolts (which ever is lesser in number). The complexity of this step is: O(XlogX) {where X = min(N,M) }
2) Now take another set (the unsorted one) and do a binary search for its position in the sorted array(the other one). Thus you only need to sort one array in this
case. Complexity of this step will be: O(YlogX) {where X is same as above & Y is max(N,M)}
Overall complexity: O(XlogX) + O(YlogX) [X,Y are defined above]
There is yet another way with complexity of O((N+M)log(N+M)) which goes like
this: mix all nuts and bolts and sort the resulting mixture. Then in the resultant
the bolt and its corresponding nut will appear adjacent to each other. This can be accomplished in O(N+M) time.
Thank you.