Nuts and Bolts Problem | Set 1

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;
}

You can also try this code with Online C++ Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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. 

You can easily run this code yourself with java online compiler.

Also check out Addition of Two Numbers in Java here.

Frequently Asked Questions

How do you perform quicksort?

In quicksort, we first select a pivot, with which comparisons are made to make two partitions. The exact process is then repeated for both the partitions until the array is sorted.

What is meant by quicksort?

Quicksort is a divide and conquer algorithm used to sort the elements in an array.

Why is quicksort called Quick?

Quicksort is called quick because it is faster than other sorting algorithms when sorting small data sets.

Is quicksort faster than bubble sort?

Yes, quicksort is faster than bubble sort.

Is merge sort better than quicksort?

Merge sort is often preferred over quicksort because of the latter’s inefficiency with large data sets.

Conclusion

In this article, we discussed about a problem named as Nuts and Bolts Problem, how it works and how to implement it, but this isn’t the end.

Keeping the theoretical knowledge at our fingertips helps us get about half the work done. To gain complete understanding, practice is a must. A variety of coding questions from interviews are available here.

Apart from this, you can also check Coding Ninjas Studio, where you’ll find thousands of other coding questions to practice and interview experiences of scholars in renowned product-based companies.

Happy learning!