Balbir's Blog: Problem 4.2 Page 85, Introduction to Algorithms
Well, it's a part of the errata of the book now. Check out http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php the errata reads
Page 85, Problem 4-2. Change the second paragraph of the problem to read, ``Show that if the only way to access information in array A is by this single-bit operation, we can still determine the missing integer in O(n) time. Any entire integer outside of A is still accessible in a single operation.''Severity level 3 is "A more significant technical or expository error"
Reported by Balbir Singh. Posted 29 November 2006.
Severity level: 3
To be corrected in the eighth printing.
I have not yet figured out how the new solution works (with the new constraint), if anybody else thinks of it, please do comment on it here.