The Nuts n Bolts Problem (Lock & Key problem)

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently.
Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

There are n nuts and corresponding bolts. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently.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.

Other way of asking this problem is, given a box with locks and keys where one lock can be opened by one key in the box. We need to match the pair.

http://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem/

Strategy:

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)