title: Faster algorithm to find unique element between two arrays?
body: <p><strong>EDIT</strong>: For anyone new to this question, I have posted an answer clarifying what was going on. The accepted answer is the one I feel best answers my question as originally posted, but for further details please see my answer.</p>
  
  <p><strong>NOTE</strong>: This problem was originally pseudocode and used lists. I have adapted it to Java and arrays. So while I'd love to see any solutions that use Java-specific tricks (or tricks in any language for that matter!), just remember that the original problem is language-independent.</p>
  
  <h2>The Problem</h2>
  
  <p>Let's say that there are two unsorted integer arrays <code>a</code> and <code>b</code>, with element repetition allowed. They are identical (with respect to contained elements) <em>except</em> one of the arrays has an extra element. As an example:</p>
  
  <pre><code>int[] a = {6, 5, 6, 3, 4, 2};
  int[] b = {5, 7, 6, 6, 2, 3, 4};
  </code></pre>
  
  <p>Design an algorithm that takes as input these two arrays and outputs the single unique integer (in the above case, 7).</p>
  
  <h2>The Solution (So Far)</h2>
  
  <p>I came up with this:</p>
  
  <pre><code>public static int getUniqueElement(int[] a, int[] b) {
      int ret = 0;
      for (int i = 0; i &lt; a.length; i++) {
          ret ^= a[i];
      }
      for (int i = 0; i &lt; b.length; i++) {
          ret ^= b[i];
      }
      return ret;
  }
  </code></pre>
  
  <p>The "official" solution presented in class:</p>
  
  <pre><code>public static int getUniqueElement(int[] a, int[] b) {
      int ret = 0;
      for (int i = 0; i &lt; a.length; i++) {
          ret += a[i];
      }
      for (int i = 0; i &lt; b.length; i++) {
          ret -= b[i];
      }
      return Math.abs(ret);
  }
  </code></pre>
  
  <p>So, both are conceptually doing the same thing. And given that <code>a</code> is of length m and <code>b</code> is of length n, then both solutions have running time of O(m + n).</p>
  
  <h2>The Question</h2>
  
  <p>I later got to talking with my teacher and he hinted that there was an even <em>faster</em> way of doing it. Honestly I don't see how; to find out whether an element <em>is</em> unique it seems you'd have to at least look at every element. At that's at least O(m + n)...right?</p>
  
  <p>So is there a faster way? And if so, what is it?</p>