You are given an array of integers. All the numbers in array occurs even number of times except the one which occurs odd number of time. You have to find the number in O(N) time and constant space.
For eg. 1,4,6,7,3,1,4,7,3,1,6 (given array)
Output: 1
Solution: Take bitwise XOR of all the elements. We will get the number with odd occurrence.
#include <stdio.h>
// function that will check for odd occurring number
int findOddOccurringNumber(int *a, int n)
{
int op = 0;
for (int i=0; i < n; i++)
op = op ^ a[i];
return op;
}
int main()
{
int a[] = {1,4,6,7,3,1,4,7,3,1,6};
int n = sizeof(a)/sizeof(a[0]);
cout << findOddOccurringNumber(a,11);
return 0;
}
Time complexity: O(N), Space Complexity: O(1)
