Find the unpaired number in an array

Question

I have an array where all the elements are repeated except one:

int[] a={2,6,6,2,4,1,4};

How can I find the element integer which is unpaired ?

Answer 1

There are a few approaches you can take:

• Approach 1 — O(n log n): sort the array. Then, iterate over the elements of the sorted array, two at a time (i=0, i=2, etc.). When a[i] and a[i+1] are unequal — or when i+1 == a.length — you know that a[i] is unpaired.
• Approach 2 — O(n²): iterate over the elements. For each element a[i], iterate over the elements (in a nested loop) and see if it ever occurs that a[i] == a[j] while i != j. If not, then a[i] is unpaired.
• Approach 3 — O(m), where m is the difference between the greatest and the least element (noting that m is Ω(n)): iterate over the elements, finding the greatest and least values MIN and MAX. Create an int[] b = new int[MAX-MIN+1]. Iterate over the elements again, incrementing b[a[i]-MIN] for each element. Then iterate over b; when you find b[j]==1, j is unpaired.

Note: You use the term "element integer", but that's not a real term. The above assumes that you mean "integer-valued element". If you actually mean "element index", then only Approach 2 can be used without modification. Approach 3 would require a little bit of adjustment, and Approach 1 would require a lot of adjustment. (Of course, once you've found the value that occurs only once, you can just iterate over the array one more time to find the index of that value — provided you still have the original array order.)

---

Edited to add: I don't know how I missed this before — I guess I'm not used to thinking of bitwise operations when writing Java — but the best solution is actually:

• Approach 4 — O(n): compute the bitwise-XOR, ^, of all the elements of the array. This is the unpaired element. You see, XOR is commutative and associative, so 2^6^6^2^4^1^4 is the same as 1^(2^2)^(4^4)^(6^6); and x^x is always 0, so the pairs always cancel either other out. You can just write:

  int result = 0;
  for(int i : a)
      result ^= i;
  

  to compute the unpaired element. (To get the index of the unpaired element, you'd then iterate over the array again, looking for result.)

Answer 2

You could use a map to keep a count of how many times a number has been seen. There are undoubtedly better ways of doing it, but it'll work.

public static void main( String[] args ) {
    int[] a = { 2, 6, 6, 2, 4, 1, 4 };

    Map<String, Integer> counts = new HashMap<String,Integer>();

    String key;
    for ( int i : a ) {
        key = String.valueOf( i );
        if ( counts.containsKey( key ) ) {
            int count = counts.get( key );
            counts.put( key, ++count );
        }
        else {
            counts.put( key, 1 );
        }
    }

    for ( Map.Entry<String, Integer> entry : counts.entrySet() ) {
        if ( entry.getValue() < 2 ) {
            System.out.println( entry.getKey() + " does not have a pair" );
        }
    }
}

Answer 3

There is an example which is listed in codility example and I test this code there and found some in correctness for some of the test cases with also bad performance