2. Suppose you are given an unsorted array A[1..n], which contains all but one o

Question

2. 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 Afi] 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* - 1 for some integer k; if so, you are free to make this assumption.

Explanation / Answer

Suppose that the input is A[]=0,1,2,3,4,5,7,8 so that 6 is missing. The numbers are sorted for convenience only, because they don't have to be sorted for the solution to work because it only works based on the significant bits.

Since n is 8 then the numbers are represented using 4 bits. From 0000 to 1000.
Here we are introducing a way to do this using partition.

1.Partition the array using the most significant bit(MSB).

You get 0,1,2,3,4,5,7 and 8. Since 8 is present, continue with the left partition.

2.Partition the sub array using the 2nd most significant bit.

You get 0,1,2,3 and 4,5,7. now continue with the partition that has odd number of elements, which is 4,5,7.

3.Partition the sub array using the 3rd most significant bit.

You get 4,5 and 7. Again continue with the partition that has odd number of elements, which is 7.

4.Partition the sub array using the 4th most significant bit you get nothing and 7.

So the missing number is 6.

Time Complexity:

The 1st partition takes n operations. The 2nd partition takes n operations. The 3rd partition takes n/2 operations. The 4th partition takes n/4 operations. And so on.

So the running time is O(n+n+n/2+n/4+...+1)<2n.
The complexity of this approach will be O(n)

Alogorithm:

1. First find k where k=no.of bits for each array element

2.

for (j=1;j<=k;j++)

{

for (i=0;i<=n-1;i++)

{

if bit(i,j)=0

{

A1[i]=A[i] //A1 is the newly created first subarray where MSB=0.

}

else

{

A2[i]=A[i] //A2 is the newly created second subarray where MSB=1.

}

}

}

This is the partitioning technique.

3.Note that one half has ceil(n/2) elements, and the other has floor(n/2) elements.

4.Repeat the process for the smaller array until you find the missing number.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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