Question

(20 points) Given a collection of n nuts and a collection of n bolts, arranged in an increasing order of size, give an O(n) time algorithm to check if there is a nut and a bolt that have the same size. The sizes of the nuts and bolts are stored in the sorted arrays NUT S[1..n] and BOLT S[1..n], respectively. Your algorithm can stop as soon as it finds a single match (i.e, you do not need to report all matches).

Answer 1

Answer:

Check the explanation

Explanation:

Keep two iterators, i (for nuts array) and j (for bolts array).

while(i < n and j < n) {

if nuts[i] == bolts[j] {

We have a case where sizes match, output/return

}

else if nuts[i] < bolts[j] {

what this means is that the size of nut is lesser than that of bolt and we should go to the next bigger nut, i.e., i+=1

}

else {

what this means is that the size of bolt is lesser than that of nut and we should go to the next bigger bolt, i.e., j+=1

}

}

Since we go to each index in both the array only once, the algorithm take O(n) time.