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.
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)