Table of Contents
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(n2), 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.
Quick Sort (Divide & Conquer algorithm)
It is a type of algorithm which divides the array into two parts using a pivot element. The idea is to place the pivot element in its correct place such that the pivot element has all elements smaller in the left side and all elements on the right side of it are greater when ascending order.
Let us see the code implementation:
#include <iostream>
using namespace std;
int partition(int *arr,int s,int e){
//partition function to make two parts of the array placing the pivot element in its correct position
int i = s-1;
for(int j = s;j<e;j++){
if(arr[j]<arr[e])
{
i = i+1;
swap(arr[i],arr[j]);
}
}
swap(arr[i+1],arr[e]);
return i+1;
}
void quicksort(int *arr,int s,int e){
if(s<e){ //checking if the s,e are in bounds
int p = partition(arr,s,e);
cout<<p<<endl;
quicksort(arr,s,p-1);
quicksort(arr,p+1,e);
}
}
void print(int arr[],int n){
for(int i = 0;i<n;i++)
cout<<arr[i]<<" ";
}
int main() {
// your code goes here
int n;
cin>>n;
int *arr = new int[n];
for(int i = 0;i<n;i++)
cin>>arr[i];
quicksort(arr,0,n-1);
print(arr,n);
return 0;
}Time Complexity: O(nlogn), where n is the number of elements in the array. After we have seen the Quicksort algorithm now let us see how this can be used to optimise our problem.
Divide and Conquer Algorithm
The idea is to make two partitions considering the bolt element as a pivot for each case, and then arranging the nuts arrays according to the condition where the elements in the nuts array which are smaller than the pivot area on the left side and the larger area on the right side.
Let us see the code implementation:
#include<iostream>
using namespace std;
int partition(char *array, int low, int high, char pivot) {
int i = low;
for(int j = low; j<high; j++) {
if(array[j] <pivot) {
swap(array[i], array[j]);
i++;
}else if(array[j] == pivot) {
char temp = array[j];
array[j] = array[high];
array[high] = temp;
j--;
}
}
char temp = array[j];
array[j] = array[high];
array[high] = temp;
return i;
}
void solve(char *nut, char *bolt[], int low, int high) {
if(low < high) {
int pivotpos = partition(nut, low, high, bolt[high]);
partition(bolt, low, high, nut[pivotpos]);
solve(nut, bolt, low, pivotpos - 1);
solve(nut, bolt, pivotpos+1, high);
}
}
int main() {
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,0,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(nlogn), where n is the number of elements in each array.
Using Hashmap
Another way of solving this problem is by using a Hashmap. The idea here is to store the bolts and their corresponding pair of nuts in a map of key-value pairs. Although this increases the space complexity but reduces the time complexity to linear order.
Code Implementation:
#include <bits/stdc++.h>
using namespace std;
// function to match nuts and bolts
void solve(char *nut, char *bolt, int n)
{
unordered_map<char, int> mp;
//storing in the map
for (int i = 0; i < n; i++)
mp[nut[i]] = i;
for (int i = 0; i < n; i++)
if (mp.find(bolt[i]) != mp.end())
nut[i] = bolt[i];
}
int main() {
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;
}Conclusion
Time Complexity: O(n), where n is the number of elements in each array.
Space Complexity: O(n), where n is the number of elements in each array. Hence, we have learned a very interesting application of quicksort and also a popular interview question.
Hope this article could explain a little more depth of the application of sorting algorithms other than just sorting and help aspiring developers and programmers. To explore more articles, check out our blog section.
By Aniruddha Guin
