title: Dealing with M occurrences among N
body: <p>Question I've been given at the job interview. I was close to the solution but did not solve it unfortunately.</p>
  
  <p>Assume we have a sequence that contains <strong><em>N</em></strong> numbers of type <code>long</code>. And we know for sure that among this sequence each number does occur exactly <strong><em>n</em></strong> times except for the one number that occurs exactly <strong><em>m</em></strong> times (<em>0</em> &lt; <strong><em>m</em></strong> &lt; <strong><em>n</em></strong>). How do we find that number with <em>O(N)</em> operations and <em>O(1)</em> additional memory?</p>
  
  <p>For the simplest case (when <strong><em>n</em></strong> = <em>2</em> and <strong><em>m</em></strong> = <em>1</em>) all that we should do is just to perform accumulative <code>xor</code> on every number in sequence. The result will be equal to the desired number. But i'm stuck while trying to deal with arbitrary <strong><em>m</em></strong> and <strong><em>n</em></strong>.</p>
  
  <p>I would appreciate an actual C++ solution.</p>
  
  <hr>
  
  <p>EDIT: We know actual values of <strong><em>m</em></strong> and <strong><em>n</em></strong> a priori.</p>
  
  <p><strong>Example.</strong> We know that <strong><em>n</em></strong> = 3 and <strong><em>m</em></strong> = 2. The sequence (<strong><em>N</em></strong> = <em>8</em>) is</p>
  
  <pre><code>5 11 5 2 11 5 2 11
  </code></pre>
  
  <p>And the right answer is <em>2</em> in this particular case because it occurs only twice.</p>