Nuts & Bolts Problem (Lock & Key problem) - GeeksforGeeks

Nuts & Bolts Problem (Lock & Key problem) - GeeksforGeeks

Nuts & 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. 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. Brute force Way: Start with the first bolt and compare it with each nut until we find a match. In the worst case we require n comparisons. Doing this for all bolts gives us O(n^2) complexity. Quick Sort Way: We can use quick sort technique to solve this. We represent nuts and bolts in character array for understanding the logic. Nuts represented as array of character char nuts[] = {'@', '#', '$', '%', '^', '&'} char bolts[] = {'$', '%',

Read full article from Nuts & Bolts Problem (Lock & Key problem) - GeeksforGeeks