$($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 $j$ th 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(lo{g}^{2}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.