# The Nuts n Bolts Problem

### 20 January, 2014 - 1 min read

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)