title: In an array with integers one value is in the array twice. How do you determine which one?
body: <p>Assume that the array has integers between 1 and 1,000,000.</p>
  
  <p>I know some popular ways of solving this problem:</p>
  
  <ol>
  <li>If all numbers between 1 and 1,000,000 are included, find the sum of the array elements and subtract it from the total sum (n*n+1/2)</li>
  <li>Use a hash map (needs extra memory)</li>
  <li>Use a bit map (less memory overhead)</li>
  </ol>
  
  <p>I recently came across another solution and I need some help in understanding the logic behind it:</p>
  
  <blockquote>
    <p>Keep a single radix accumulator. You exclusive-or the accumulator with
    both the index and the value at that index. </p>
    
    <p>The fact that x ^ C ^ x == C is useful here, since each number will be
    xor'd twice, except the one that's in there twice, which will appear 3
    times. (x ^ x ^ x == x) And the final index, which will appear once.
    So if we seed the accumulator with the final index, the accumulator's
    final value will be the number that is in the list twice.</p>
  </blockquote>
  
  <p>I will appreciate it if some one can help me understand the logic behind this approach (with a small example!).</p>