Last Updated: 7 Nov, 2020
Nuts and Bolt Problem
Easy
Asked in company
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. Your task is to find the correct match of nuts and bolts from the given set and assign a nut to a bolt when it is matched.
Note:
1. A 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.
2. The set of Nuts/Bolts will consist of numeric strings that represent their sizes. The size of each nut/bolt will be equal to its numerical value. For example, the size of ‘10’ will be equal to 10.
3. For every bolt, there will exist a nut of the same size.
4. Don’t return or print anything. Modify the original sequence of nuts and bolts such that each nut of a particular size matches its bolt of the same size.
5. Store the matched pair of nuts and bolts in any order.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘3*T’ lines represent the ‘T’ test cases.
The first line of each test case contains an integer ‘N’ denoting the number of nuts/bolts.
The second line of each test case contains ‘N’ space-separated strings denoting the nuts of different sizes.
The third line of each test case contains ‘N’ space-separated strings denoting bolts of different sizes.
Output Format:
For each test case, 2 arrays will be printed on separate lines such that the first array contains the nuts, the second array contains the bolts and the nut present at the ‘ith’ position in the array of nuts should be a perfect match for the bolt present at the ‘ith’ position in the array of bolts.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 5 * 10^3
1 <= SIZE <= 10^9
Time limit: 1 second
Approaches
The idea is to quick sort the two arrays using each other.
- Pick the last element of the bolts array as the pivot.
- Using the pivot, rearrange the array of nuts such that all the nuts smaller than the pivot are on the left side and all the greater nuts are on the right side. This can be done as follows:
a. Pass the nuts array, 0 as ‘LOW’, (SIZE-1) of the nuts array as ‘HIGH’, and the pivot obtained from the bolts array to the function ‘PARTITION’.
b. In the function ‘PARTITION’, a pointer is fixed at the pivot element. The second pointer is fixed at the first index. The pivot element is compared with all the elements starting from the first index. If the element smaller than the pivot element is reached, swap the element with the second pointer and increment the second pointer.
c. If the element is the same as the pivot element, swap it with the last element.
d. The process goes on until the second last element is reached. Finally, the pivot element is swapped with the second pointer.
e. Now the left and right subparts of this pivot element are taken for further processing in the steps below
Return the index of the pivot in the nuts array. Call it ‘i’.
3. Now, using NUTS[i] as a pivot in the bolts array, partition the bolts array.
4. Recur for [LOW……PIVOT-1] and [PIVOT+1…….HIGH] for nuts and bolts array.
5. Lastly, we get the required pairs.