title: Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
body: <p>I had an interesting job interview experience a while back. The question started really easy:</p>
  <blockquote>
  <p><strong>Q1</strong>: We have a bag containing numbers <code>1</code>, <code>2</code>, <code>3</code>, …, <code>100</code>. Each number appears exactly once, so there are 100 numbers. Now one number is randomly picked out of the bag. Find the missing number.</p>
  </blockquote>
  <p>I've heard this interview question before, of course, so I very quickly answered along the lines of:</p>
  <blockquote>
  <p><strong>A1</strong>: Well, the sum of the numbers <code>1 + 2 + 3 + … + N</code> is <code>(N+1)(N/2)</code> (see <a href="http://en.wikipedia.org/wiki/Arithmetic_sum#Sum" rel="noreferrer">Wikipedia: sum of arithmetic series</a>). For <code>N = 100</code>, the sum is <code>5050</code>.</p>
  <p>Thus, if all numbers are present in the bag, the sum will be exactly <code>5050</code>. Since one number is missing, the sum will be less than this, and the difference is that number. So we can find that missing number in <code>O(N)</code> time and <code>O(1)</code> space.</p>
  </blockquote>
  <p>At this point I thought I had done well, but all of a sudden the question took an unexpected turn:</p>
  <blockquote>
  <p><strong>Q2</strong>: That is correct, but now how would you do this if <em>TWO</em> numbers are missing?</p>
  </blockquote>
  <p>I had never seen/heard/considered this variation before, so I panicked and couldn't answer the question. The interviewer insisted on knowing my thought process, so I mentioned that perhaps we can get more information by comparing against the expected product, or perhaps doing a second pass after having gathered some information from the first pass, etc, but I really was just shooting in the dark rather than actually having a clear path to the solution.</p>
  <p>The interviewer did try to encourage me by saying that having a second equation is indeed one way to solve the problem. At this point I was kind of upset (for not knowing the answer before hand), and asked if this is a general (read: &quot;useful&quot;) programming technique, or if it's just a trick/gotcha answer.</p>
  <p>The interviewer's answer surprised me: you can generalize the technique to find 3 missing numbers. In fact, you can generalize it to find <em>k</em> missing numbers.</p>
  <blockquote>
  <p><strong>Qk</strong>: If exactly <em>k</em> numbers are missing from the bag, how would you find it efficiently?</p>
  </blockquote>
  <p>This was a few months ago, and I still couldn't figure out what this technique is.  Obviously there's a <code>Ω(N)</code> time lower bound since we must scan all the numbers at least once, but the interviewer insisted that the <em>TIME</em> and <em>SPACE</em> complexity of the solving technique (minus the <code>O(N)</code> time input scan) is defined in <em>k</em> not <em>N</em>.</p>
  <p>So the question here is simple:</p>
  <ul>
  <li>How would you solve <strong>Q2</strong>?</li>
  <li>How would you solve <strong>Q3</strong>?</li>
  <li>How would you solve <strong>Qk</strong>?</li>
  </ul>
  <hr />
  <h3>Clarifications</h3>
  <ul>
  <li>Generally there are <em>N</em> numbers from 1..<em>N</em>, not just 1..100.</li>
  <li>I'm not looking for the obvious set-based solution, e.g. using a <a href="http://en.wikipedia.org/wiki/Bit_array" rel="noreferrer">bit set</a>, encoding the presence/absence each number by the value of a designated bit, therefore using <code>O(N)</code> bits in additional space. We can't afford any additional space proportional to <em>N</em>.</li>
  <li>I'm also not looking for the obvious sort-first approach. This and the set-based approach are worth mentioning in an interview (they are easy to implement, and depending on <em>N</em>, can be very practical). I'm looking for the Holy Grail solution (which may or may not be practical to implement, but has the desired asymptotic characteristics nevertheless).</li>
  </ul>
  <p>So again, of course you must scan the input in <code>O(N)</code>, but you can only capture small amount of information (defined in terms of <em>k</em> not <em>N</em>), and must then find the <em>k</em> missing numbers somehow.</p>