Let n = 2^k - 1 for some integer k greaterthanorequalto 1. You are given an unso

Question

Let n = 2^k - 1 for some integer k greaterthanorequalto 1. 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 0 (n) times. Each element of A is represented in binary using k bits, and the only way to access the elements is to call the function bit (i, j). Which returns the value of the bit of (In other words, you cannot directly access an element A[i].) Give a divide and conquer algorithm for this problem that finds the missing number while making; at most O (n) calls to the function bit. Give a brief (3-4 line) argument of correctness for your algorithm. Give a recurrence for the number of times your algorithm calls bit. Solve it to obtain the running time in asymptotic notation. No explanation is necessary.

Explanation / Answer

There are k bits in each array element. We can use combination of partition based selection algorithm and radix-sort.

The complexity of this approach will be n + n/2 + n/4 + ... + 1 < 2n, so it is O(n)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.