Q. There are n nuts and corresponding bolts. However, all nuts and bolts are shuffled and we have to device a technique to pair them.

- No two pairs are of same size.
- Each nut has exactly one bolt for it.
- You can’t compare nut with a nut and same with bolt.
- You can determine by a comparison if a nut is greater or a bolt is greater.

A. This problem can also be solved in a quick sort kind of technique.

- Pick up nut n1 with all bolts. Divide all bigger bolts on one side and smaller bolt on other side. One bolt say b1 matches n1 to make the pair.
- Take nut n2 and compare with bolt b1. If bigger bolt is required look in greater set otherwise in the smaller set.
- Do the same with rest of the nuts. This way we are saving the number of comparisons by categorizing.

Time complexity is approximately O(nlogn)

### Like this:

Like Loading...

*Related*

There are N nuts and N bolts. All are of different size and each nut has a bolt for it.So, Just sort both of them.Then one-one mapping!

Sorting happens in the process (answer). If you sort both of them individually it takes more time

Also as the question clearly states that you are not allowed to compare a nut with another nut, or a bolt with another bolt, its inherently impossible to sort them initiaaly.

The approach mentioned is a brainy workaround , and does almost the same thing in the same time.

@Badrinath: You can’t compare nut with nut (bcoz of Rule 3) and hence can’t sort . So your method is INVALID.

@Harsh : Sorting twice is still O(nlogn) if sorting once cost you O(nlogn).

yes ur method is wrong. As u are sorting bolts , before comparing nut n1 with bolt b1.

Anyone has a better method, other than comparing each nut to each and every bolt ?

Thanks.

I dont see any things wrong with the approch though, still this approch may not be optimal always, it depends on number of nuts and bolts given and size of the first pick.

Please feel free to put your thoughts on how it can be optimized.

This method is actually performing merge sort so, its worst case will be n squared complexity (when he always picks up smallest or largest nut) and best will be nlogn when he picks up middlemost nut evey time

Sorry for the error I meant quick sort

Quick sort performs in o(nlogn) even for worst case.