title: Finding EVEN number of times repeating integer in an array where rest of the integers repeat ODD number of times
body: <p>Given is an array of integers. Each number in the array occurs an ODD number of times, but only 1 number is occurring an EVEN number of times. Find that number.</p>
  
  <p>Below is the solution I read on stackoverflow that does NOT work. I am unable to find the link to that solution and I was wondering if somebody could help me understand why this solution is incorrect unless I am doing something wrong below.</p>
  
  <p>We first XOR all the elements in the array. Lets call it <code>aWithOutDuplicate</code> which contains all the odd elements except for duplicate one. We then OR all the elements. Lets call it <code>aAllUnique</code>that should contain all the unique elements. XORing <code>aWithOutDuplicate</code> and <code>aAllUnique</code>should spit out the duplicate element.</p>
  
  <pre><code>    int arr[] = {1,2,3,4,5,6,7,8,4,9};
      int aWithOutDuplicate = 0;
      int aAllUnique = 0;
  
      for(int i=0;i&lt;arr.length;i++) {
        aWithOutDuplicate ^= arr[i];
        aAllUnique |= arr[i];
      }
  
     cout &lt;&lt; (aWithOutDuplicate ^ aAllUnique);
  </code></pre>
  
  <p>Update:
  I wonder if this problem can be solved in O(n) time and O(1) space complexity.</p>