title: Find duplicate element in array in time O(n)
body: <p>I have been asked this question in a job interview and I have been wondering about the right answer.</p>
  
  <blockquote>
    <p>You have an array of numbers from 0 to n-1, one of the numbers is removed, and replaced with a number already in the array which makes a duplicate of that number. How can we detect this duplicate in time <em>O(n)</em>?</p>
  </blockquote>
  
  <p>For example, an array of <code>4,1,2,3</code> would become <code>4,1,2,2</code>.</p>
  
  <p>The easy solution of time <em>O(n<sup>2</sup>)</em> is to use a nested loop to look for the duplicate of each element.</p>