title: Finding the missing number - from Programming Pearls 2nd Edition
body: <p>From the book Programming Pearls 2nd Edition, quoting the question A from Column 2, section 2.1 </p>
  
  <blockquote>
    <p>Given a sequential file that contains at most four billion integers in
    random order, find a 32-bit integer that isn't in the file (and there
    must be at least one missing - why ?). How would you solve this
    problem with ample quantities of main memory ? How would you solve it
    if you could use several external "scratch" files but only a few
    hundred bytes of main memory ?</p>
  </blockquote>
  
  <p>The problem statement says "at most" four billion integers. So one valid input could be in the range 100 - 299 with one missing number. If this understanding of the problem statement is correct then the required inputs for this problem are the file containing the numbers and also the range of the numbers in the file, ie: i to n.</p>
  
  <p>For this problem isn't the following O(n) solution more intuitive than the one given in the book (from Ed Reingold) ? Or am I missing something ?</p>
  
  <p>Assume the given range is i...n</p>
  
  <pre><code>using the forumla (n * (n + 1) / 2) 
    x = the sum of numbers from 1 to i-1 
    y = the sum of numbers from 1 to n 
  walk through the input and get a sum of the numbers (value z)
  
  missing number = (y - x - z)
  </code></pre>