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

Question

Suppose you are given an unsorted array A[1..n], which contains all but one of the n + 1 integers in the range 0, . . . , n (so exactly one of these elements is missing from A). To simplify the problem somewhat, we will assume that n = (2^k) 1 for some integer k. Hence each array element has a binary representation using k bits.

You want to determine the missing integer. You are not allowed to access an entire integer in A with a single operation. The only way to access the elements of A is by calling the function bitvalue(i, j), which returns the value of the jth bit of A[i]. Give a divide-and-conquer algorithm that finds the missing integer and makes only O(n) calls to the function bitvalue().

Note: There are (n 1) log n bits, so you cannot afford to look at every bit.

Explanation / Answer

I am writing the code with the variables n and k and I am assuming that the bitvalue function is already exists and I can simply using that function.

n ----> array element

k ----> no.of bits 2 represent n

#include<stdio.h>

#include<math.h>

void main()

{

int i, j, n, k, result, result1[ n ] ;

   double p ;

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

{

p = 0.00 ;

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

   {

result =+ (bitvalue(i , j) * pow( 2.0 , p) ) ;

p = p + 1.00 ;

   }

result1[ result ] = result ;

   }

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

   {

   if( result1[ i ] != i )

   {

printf("The missing number is : %d ",i) ;

break ;

   }

}

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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