How to find 4 byte number that was absent in input?
<p>I have such task, and actually have no idea how to start.
On the input I have a huge array of 4-byte positive numbers. Numbers can be repeated. I know that one of the number is not included in the input array. How can I find this number, using minimum resources?</p>

<p>I go with Dan Getz assumption of the problem. Dan's solution gives you in the worst case O(n log n) runtime. </p>

<p>Now the crazy idea:
How about skipping the sorting part that is the "heaviest" overhead O(n log n)? Instead of starting with the sorting, just maintain a <code>Hashmap</code> of ALL 4 byte positive integers with integer itself as a key and <code>false</code> as the default value. 
Some pseudo code:</p>

<p><strong>start</strong></p>

<pre><code>foreach number in the input:
   if the number is in the valid range:
      if the corresponding hashmap entry has the value set to `false`, toggle it to `true`
      otherwise, do nothing and skip to the next input
foreach Hashmap entry
      if the value is `false` return the key of that entry
</code></pre>

<p><strong>end</strong></p>

<p>The size of the Hashmap is smaller or equal to the size of the input (n).
The runtime complexity in the worst case O(n)
Memory-wise you will need an additional O(n) of memory. Most likely it will be worse than for Dan Gretz solution (depends what sorting algorithm he uses, if I assume the normal Merge sort, then probably my solution will waste more memory most of the time and will waste the same or less amount of memory only during the last step of merge sort)</p>

python algorithm