title: Finding an element in an array that isn't repeated a multiple of three times?
body: <p>After reading <a href="https://stackoverflow.com/questions/7338070/finding-an-element-in-an-array-where-every-element-is-repeated-odd-number-of-time">this interesting question</a> I was reminded of a tricky interview question I had once that I never satisfactorily answered:</p>
  
  <blockquote>
    <p>You are given an array of n 32-bit unsigned integers where each element (except one) is repeated a multiple of three times.  In O(n) time and using as little auxiliary space as possible, find the element of the array that does not appear a multiple of three times.</p>
  </blockquote>
  
  <p>As an example, given this array:</p>
  
  <blockquote>
    <p>1 1 2 2 2 3 3 3 3 3 3</p>
  </blockquote>
  
  <p>We would output 1, while given the array</p>
  
  <blockquote>
    <p>3 2 1 3 2 1 2 3 1 4 4 4 4</p>
  </blockquote>
  
  <p>We would output 4.</p>
  
  <p>This can easily be solved in O(n) time and O(n) space by using a hash table to count the frequencies of each element, though I strongly suspect that because the problem statement specifically mentioned that the array contains 32-bit unsigned integers that there is a much better solution (I'm guessing O(1) space).</p>
  
  <p>Does anyone have any ideas on how to solve this?</p>