title: Tricky algorithm question
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers">Quickest way to find missing number in an array of numbers</a>  </p>
  </blockquote>
  
  
  
  <p>Input: unsorted array A[1,..,n] which contains all but one of the integers in the range 0,..,n</p>
  
  <p>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 A[i] and takes constant time.</p>
  
  <p>Any ideas?  I think some sort of divide-and-conquer algorithm would be proper, but I can't think of what exactly I should do.  Thanks in advance!</p>