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))`.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <algorithm> using namespace std; // Function to find odd occurring element in a given array int findOddOccuring(int arr[], int n) { // sort the array sort(arr, arr + n); // traverse the array from the beginning int i = 0; while (i < n) { // store the current element int curr = arr[i]; // find count of the current element int count = 0; while (i < n && arr[i] == curr) { count++; i++; } // if count of the current element is odd, return it if (count & 1) return curr; } // invalid input return -1; } int main() { int arr[] = { 2, 2, 1, 1, 3, 3, 2, 2, 4, 4, 3, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "The odd occurring element is " << findOddOccuring(arr, n); return 0; } |

`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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <stdio.h> // Function to find odd occurring element in a given array int findOddOccuring(int arr[], int n) { int xor = 0; for (int i = 0; i < n; i++) xor = xor ^ arr[i]; return xor; } int main(void) { int arr[] = { 2, 2, 1, 1, 3, 3, 2, 2, 4, 4, 3, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); printf("The odd occurring element is %d ", findOddOccuring(arr, n)); return 0; } |

`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:

1 2 |
arr[] = { 2, 2, 1, 1, 3, 3, 2, 2, 4, 4, 3, 1, 1 } pos[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } |

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:

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <stdio.h> // Recursive function to find an odd occurring element in an array // using binary search. This function assumes the input is valid. int findOddOccuring(int arr[], int low, int high) { // base case if (low == high) { return low; } // find the middle index int mid = (low + high) / 2; // if mid is odd if (mid & 1) { // if element before mid is same as mid element, the odd element // lies on the right side; otherwise it lies on the left side if (arr[mid] == arr[mid - 1]) return findOddOccuring(arr, mid + 1, high); else return findOddOccuring(arr, low, mid - 1); } // mid is even else { // if element next to mid is same as mid element, the odd element // lies on the right side; otherwise it lies on the left side if (arr[mid] == arr[mid + 1]) return findOddOccuring(arr, mid + 2, high); else return findOddOccuring(arr, low, mid); } } // main function int main(void) { int arr[] = { 2, 2, 1, 1, 3, 3, 2, 2, 4, 4, 3, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); int index = findOddOccuring(arr, 0, n - 1); printf("The odd occurring element is %d ", arr[index]); return 0; } |

`Output:`

The odd occurring element is 3

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply