Algorithm to find odd item (with no pairs) in an array? [duplicate]

This question already has answers here: Closed 12 years ago.

Possible Duplicate:

Finding a single number in a list

What to be a good algorithm given an array of integers, all but one of which appears an even number of times, find the one integer which appears an odd number of times.

Perhaps something along the lines of binary search like sum all开发者_C百科 elements of 2 small arrays of n/2 size, compare recursively find out?

Edit:

Is this XOR algorithm actually assuming {1,1,4,4,7,7,5,8,8,9,9}? My input can be randmon too - { 1,4,1,8,9,5,4,5,9,8}. So the logic changes in that case?

---

XOR all the array elements. The result will be the element that repeats odd number of times.

---

XOR the elements. Because each number appears once, the bits that represent it will toggle back and forth, and you'll be left with only the bits that represent the only number that didn't appear twice.

[TestMethod]
public void SumOfPairs()
{
    var nums = new[] { 1, 1, 4, 4, 7, 7, 5, 8, 8, 12, 12 };
    int i = 0;
    foreach (var num in nums)
    {
        i ^= num;
    }

    Assert.AreEqual(5, i);
}

Note that this doesn't work unless the exact conditions you specified exist.

---

Exclusive or them all together.

---

Just xor all numbers in the array. The result is the number which appears odd times. This is true because a number xor the same number gives 0. If you run it even times the result is again 0. But if you run it odd times the result is 0 xor number = number.

---

xor all the items in the array.

---

dude, do an xor on the set of all the integers. If any particular integer appears an odd number of times, this will be the result