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)