The Nuts n Bolts Problem

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.

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)