title: O(n) algorithm to find the odd-number-out in array of consecutive integers from 1 to n(not odd numbers)
body: <p>I'm having a great deal of trouble trying to figure this question out, and the root of that trouble is creating an algorithm of <code>O(n)</code> complexity. Here's the question I'm struggling with:</p>
  <blockquote>
  <p>An Array <code>A</code> of length <code>n</code> contains integers from the range <code>[0, .., n - 1]</code>. However, it only contains <code>n - 1</code> distinct numbers. So one of the numbers is missing and another number is duplicated. Write a Java method that takes <code>A</code> as an input argument and returns the missing number; the method should run in <code>O(n)</code>.</p>
  <p>For example, when <code>A = [0, 2, 1, 2, 4]</code>, <code>oddOneOut()</code> should return <code>3</code>; when <code>A = [3, 0, 0, 4, 2, 1]</code>, <code>oddOneOut()</code> should return <code>5</code>.</p>
  </blockquote>
  <p>Obviously this is an easy problem to solve with an <code>O(n<sup>2</sup>)</code> algorithm, (and most likely <code>O(n)</code>, I'm just not seeing it!). I've attempted to solve it using all manner of methods, but to no avail. I'm attempting to solve it in Java, but if you're more comfortable solving it Python, that would be fine as well.</p>
  <p>Thank you in advance...</p>