Find the odd occurring element in log(n) time

Given an array of integers where every element appears even number of times except one element which appears odd number of times, find that odd occurring element in O(log(n)) time and constant space. The equal elements must appear in pairs in the array but there cannot be more than two consecutive occurrences of an element.

For instance, both these arrays are invalid – {1, 2, 1} and {1, 1, 2, 2, 2, 3, 3}. The first one doesn’t have equal elements appear in pairs and the second one contains three consecutive instances of an element. On the other hand, the array {2, 2, 3, 3, 2, 2, 4, 4, 3, 1, 1} is valid and the odd occurring element present in it is 3.

The naive solution is to sort the array and count occurrence of each element by traversing the sorted array. We return the element with odd count. The time complexity of this solution is O(nlog(n)).

Output:

The odd occurring element is 3

We can solve this problem in linear time using the XOR operator. The idea is to take XOR of all elements present in the array. The even occurring elements will cancel each other and we are left with the only odd occurring element.

Output:

The odd occurring element is 3

We can even solve this problem in O(log(n)) time.

As per problem constraints, equal elements appears in pairs in the array and there cannot be more than two consecutive occurrences of any element. So there must be a single occurrence of the odd element somewhere in the array. We can find this odd occurrence using binary search algorithm.

Consider below array with their positions:

If we carefully observe, each pair of element before the odd occurring element has first occurrence at even index and the second occurrence at odd index. And each pair of element after the odd occurrence has first occurrence at odd index and the second occurrence at even index.

We can use above observation to determine which side of the mid index the odd occurring element lies. We have two cases:

1. Mid index is odd: If the element before the mid index is same as the mid element, the odd element lies on the right side; otherwise it lies on the left side.

2. Mid index is even: If the the element next to the mid index is same as the mid element, the odd element lies on the right side; otherwise it lies on the left side.

The algorithm can be implemented as follows in C:

Output:

The odd occurring element is 3

(1 votes, average: 5.00 out of 5)