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.
Thanks,
Regards
Anil.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
