Suppose you are given an unsorted array A[1..n], which contains all but one of the integers in the range 0,...,n (so exactly one of these elements is missing from A). The problem is to determine the missing integer in O(n) time. Each element of A is represented in binary, and the only operation available is the function bit(i,j), which returns the value of the jth bit of A[i] and takes constant time. Show that using only this operation, it is still possible to determine the missing integer in O(n) time, by giving a divide-and-conquer algorithm. Be sure to explicitly state and then solve the recurrence equation for the running time of your algorithm. (It may simplify your answer if you assume that n is of the form 2^k 1 for some integer k; if so, you are free to make this assumption.)