(a) Your friend, John, is holding an integer array A[1..n], and he tells you that the...

Transcribed Image Text:

(a) Your friend, John, is holding an integer array A[1..n], and he tells you that the array is sorted, and contains all the integers from 0 to n except one. John challenges you to find the missing integer. He allows you to ask him questions in the form: "What is the jth bit of A[i]?" and he is going to answer you honestly. So, you can vary the values of i and j in each question you ask him. Design an efficient algorithm to find out the missing integer using O(log n) questions. (b) Now, John has changed the input, and the array A becomes unsorted. Design an algorithm using O(n) questions to find out the missing integer. (a) Your friend, John, is holding an integer array A[1..n], and he tells you that the array is sorted, and contains all the integers from 0 to n except one. John challenges you to find the missing integer. He allows you to ask him questions in the form: "What is the jth bit of A[i]?" and he is going to answer you honestly. So, you can vary the values of i and j in each question you ask him. Design an efficient algorithm to find out the missing integer using O(log n) questions. (b) Now, John has changed the input, and the array A becomes unsorted. Design an algorithm using O(n) questions to find out the missing integer.