There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration (comparision). All the nuts/bolts might have different diameter.
The only thought comes in my mind is of O(n2) solution …Can we do better ?
can u explain please your question briefly with constraints.
This might be helpful:
The very first solution that came to my mind is O(NLOGN), sort all the bolts. For every nut size, use binary search and find the corresponding bolt.
Okay, so I after little more thinking and surfing, what I got is this:
O(N) solution with added O(N) space complexity: We may create a hash of all the bolts and then search for the corresponding bolt of the nut. This solution works fine within some range of n (not too large) and when the characteristics of the bolts are specified properly which will help you identify it uniquely.
Pseudocode something like this:
// assuming definiton of bolt as:
pair<char,int>b;
map<pair<char,int>, bool>exist;
// insert all the bolts in map
for( i in range 0,n)
see if flag = exist[bolt for nut[i]]==1
if flag:
then yes
else:
no
O(nlogn) approach:
(The solution assumes the constraint that the comparison of like items are not allowed, I got this complete definition of problem on net everywhere)
We use a divide-and-conquer algorithm very similar to randomized quicksort. The algorithm first performs a partition operation as follows: pick a random nut N[i]. Using this nut, rearrange the array of bolts into three groups of elements: first the bolts smaller than N[i], then the bolt that matches N[i], and finally the bolts larger than N[i]. Next, using the bolt that matches N[i] we perform a similar partition of the array of nuts. This pair of partitioning operations can easily implemented in Θ(n) time, and it leaves the nuts and bolts nicely partitioned so that the “pivot” nut and bolt are aligned with each-other and all other nuts and bolts are on the correct side of these pivots — smaller nuts and bolts precede the pivots, and larger nuts and bolts follow the pivots. Our algorithm then finishes by recursively applying itself to
the subarrays to the left and right of the pivot position to match these remaining nuts and bolts. We can assume by induction on n that these recursive calls will properly match the remaining bolts.
The running time of the algorithm is the 0(Nlogn).
The pseudocode will go something like this:
matchnuts(nuts[low,high], bolts[low,high])
{
// select a random nut from all the nuts in the given range
select= random(nuts[low],nuts[high]);
// partition the bolts as per this selected nut
pivot = partition(bolts, nuts[select]);
// now the bolts[pivot] and nuts[select] match, so partition the nuts array as per this pivot bolt
p = partition(nuts,bolt[pivot]);
// this p and pivot will however be same cuz for every unique nut, we have one bolt.
// now nuts[p] and bolts[pivot] match
// solve the subproblems
matchnuts(nuts[low,pivot-1],bolts[low,pivot-1];
matchnuts(nuts[pivot+1,high], bolts[pivot+1,high]);
}