title: m integers missing from an array of size n
body: <p>This is an interesting question I had come across a while ago and had some trouble solving it.</p>
  
  <blockquote>
    <p>There's an unsorted integer array of size <strong>N</strong> stored with numbers <em>1,2..,N+M</em>
    , with <strong>M</strong> integers missing from it. <strong>M</strong> and <strong>N</strong> are known before hand. Write an algorithm to find the missing <strong>M</strong> integers in the most efficient manner.</p>
  </blockquote>
  
  <p>Had tried mapping it to an array of size <strong>N</strong> + <strong>M</strong>, so that the <em>i</em> th index contains the element with value <em>i</em>, but this requires 2 scans (1 for mapping, 1 for finding the <strong>M</strong> missing numbers).</p>
  
  <p>The book in which I came across this mentions a single scan solution is possible but I was not able to arrive at it. Any ideas on how to go about this ?</p>