Number occurring odd times

Recall the challenge you solved in the "XOR operator" lesson in which we used the properties of XOR. The question which we will solve in this lesson is quite similar to that challenge. So, the problem we are going to look into is-

Find the element occurring odd times in the given array.

So, you will be given an array containing some integer elements. Out of those elements, all the other elements occur even number of times except for one element.

Let's say we have an array int Arr[11] = { 2, 5, 6, 6, 6, 4, 5, 2, 5, 4, 5}.

In this array,

• '2' appears two times (even).
• '5' appears four times (even).
• '6' appears three times (odd).
• '4' appears two times (even).

So here it the number '6' which is appearing odd times. And this is what we need to find in the question, the number that appears odd times in the array.

As we saw in "XOR" operator lesson that for a number 'x',

• x ⊕ x = 0 ( where '⊕' symbol represents XOR operation)
• x ⊕ 0 = x

So, on using the first property all the elements that appear even times when xor'd will produce 0 and using the second property we will be left with the number that appeared odd times.

So, basically xor'ing all the elements of the array will eventually provide us the output. And that's it, that's the solution of the problem. Easy, right?

Time complexity for this problem is O(n) as we have to traverse the whole array and xor all its elements.