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

Question

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 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?

Oh I proposed this binary search since I mistook the array to have identical elements except the odd one , like identical ball example - in which case binary would probably be good ! XOR seems interesting . — Nishant, Feb 03 '11 at 08:09
Would this algorithm of XOR work if the elements are randomly stored but one is ODD one . — Nishant, Feb 03 '11 at 08:23
Try it out yourself by hand, it will help you see how it works. — AakashM, Feb 03 '11 at 08:27
Aakash you mean the logic works for both random elements and for ordered elements ? {1,1,4,4,7,7,5,8,8,9,9} { 1 ,4,1,8,9,5,4,5,9,8} . I need to brush lot of fundas ...This is the doubt I have instantly without going to detials . — Nishant, Feb 03 '11 at 08:32
Many duplicates on SO already, e.g. [Finding a single number in a list](http://stackoverflow.com/questions/35185/finding-a-single-number-in-a-list) — Paul R, Feb 03 '11 at 08:51

score 11 · Accepted Answer · answered Feb 03 '11 at 08:01

11

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

answered Feb 03 '11 at 08:01

codaddict

445,704
82
492
529

Is this the case if the elements are randomny stored ? Not just pairs ? – Nishant Feb 03 '11 at 08:22
1

@Nishant: The order of the elements does not matter. Try it out yourself `arr = [1 2 3 2 1]` – codaddict Feb 03 '11 at 08:29

score 7 · Answer 2 · answered Feb 03 '11 at 08:04

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.

score 3 · Answer 3 · answered Feb 03 '11 at 08:01

3

Exclusive or them all together.

answered Feb 03 '11 at 08:01

Ian Mercer

38,490
8
97
133

score 3 · Answer 4 · answered Feb 03 '11 at 08:03

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.

score 2 · Answer 5 · answered Feb 03 '11 at 08:01

2

xor all the items in the array.

answered Feb 03 '11 at 08:01

zvrba

24,186
3
55
65

score 2 · Answer 6 · answered Feb 03 '11 at 08:02

2

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

answered Feb 03 '11 at 08:02

gprasant

15,589
9
43
57

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

6 Answers6

Linked