**Introduction**

In this article, we will be discussing an exciting problem that is very popular in developer interviews. This is the well-known Nuts and Bolts problem.

Itâ€™s quite easy to solve the problem in the brute force approach but and a slight twist of an idea that directly comes from sorting is used to optimize the code for this problem. Let us first see the problem statement.

**Problem Statement**

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 a nut to see which one is bigger/smaller.

Another 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 and we cannot match locks with locks or keys with keys.

**Brute Force Approach**

The brute force idea is to traverse the bolts/nuts array for each of the nuts/boltâ€™s elements i.e., for each nut there will be n comparisons in the worst case and vice versa.

**Code Implementation:**

```
#include <iostream>
using namespace std;
// 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.
void solve(char *nut, char *bolt, int n){
for(int i = 0;i<n;i++){
//O(n^2) approach , we cannot compare bolts and bolts as well as nuts and nuts
//elese we could have just sorted the two arrays
char curr_nut = nut[i];
for(int j = i;j<n;j++){
if(bolt[j] == curr_nut){
//swap bolt[i] & bolt[j]
int temp = bolt[i];
bolt[i] = bolt[j];
bolt[j] = temp;
break;
}
}
}
}
int main() {
// your code goes here
int t;
cin>>t;
while(t--){
int n;
cin>>n;
char *bolt = new char[n];
char *nut = new char[n];
for(int j = 0;j<n;j++)cin>>nut[j];
for(int i = 0;i<n;i++)cin>>bolt[i];
solve(nut,bolt,n);
for(int j = 0;j<n;j++)cout<<nut[j]<<" ";
cout<<endl;
for(int i = 0;i<n;i++)cout<<bolt[i]<<" ";
}
return 0;
}
```

**Time Complexity: ****O(n^2)****,** where n is the number of elements in the array each. Well, the brute force approach is quite slow, so to optimise it we will be using a very interesting algorithm- Divide & Conquer using the **QuickSort **technique.

Let us first see the quicksort algorithm.