anil kumar wrote: > An array A[1..n] contains all the integers from 0 to n except one. It > would be easy to determine the missing integer in O(n) time by using an > auxilary array B[0..n] to record which numbers appear in A. In this > problem however we cannot access an entire integer in A with a single > operation. The elements of A are represented in binary, the only > operation we can use to access them is " Fetch the jth bit of A[i] " , > which takes constant time. Find the missing integer in O(n) time using > only that operation.
Are you permitted to swap array entries in constant time? If so, the following is a solution. I'll assume n is a power of 2 for simplicity (but the idea easily extends to arbitrary n). Scan through the leading bits of the n integers. The missing integer starts with 0 if 0 appears an odd number of times, and 1 otherwise. Move all the integers starting with the same leading bit as the missing integer to one side of the array (e.g., ala partitioning in quicksort). Now recur on those remaining integers and the next most significant bit. There are lg n phases since the number of bits per integer is lg n, but the overall running time is still linear: n + n/2 + n/4 + ... --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
