Lonely Integer - XOR Integer Pairs

From Hacker Rank, Lonely Integer Challange

Taking an array of integers, where it a guarenteed that the size is odd, and all enteries bar one is a pair, return the integer that only appears once.

I knew there must be a trick to this however I didn’t figure it out. I implemented a basic solution using a map to count instances which was obviously O(N) in time.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

count := make(map[int32]int)

 for i:=0; i < len(a); i++ {

	 count[a[i]]++

 } 

 for k,v := range count {

	 if(v == 1){
	
	 return int32(k)
	
	 } 

 }

 return -1

However since there are always pairs of numbers, it is much faster to do a bitwise XOR operation, as the pairs of numbers. As a small proof:

1
2
3
4
5
6
7

1 0001					4 0100
2 0010 ^= 0011			5 0101 ^= 0001
3 0011 ^= 0000			3 0011 ^= 0010
2 0010 ^= 0010			3 0011 ^= 0001
1 0001 ^= 0011			5 0101 ^= 0100

r = 0011 = 3			r = 0100 = 4

So the resulting code will be much quicker and easier

1
2
3
4
5
6
7
8
9

 var r int32 = 0

 for i:=0; i < len(a); i++ {

	 r ^= a[i]

 } 

 return r