 |
|
 |
|
|
|
Problem: You are given an array of n integers. All the integers occur even number of times except one. Find this integer with O(n) time and O(1) additional space.
Solution: Due to the time and space required, it's not possible to finish this job by counting the number of occurrences for each integer of the array. An intuition that it's the combination of scan (O(n) time required) and some kind of arithmetic operator. XOR, yes, Exclusive OR, that's the operator I want! For integers A, B and C, A XOR B XOR C == B iff A == C.
OK, here comes my solution (C++ style):
/*-
- theArray array for the integers
- n length of the array
-*/
int GetSpecialOne(int *theArray, int n)
{
assert(n > 0);
int nSpecialOne = theArray[n - 1];
for (int i = n - 2; i >= 0; i --) {
nSpecial ^= theArray[i];
}
return nSpecial;
}
