Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.
Example:
I/P = [1, 2, 3, 2, 3, 1, 3]
O/P = 3
Approach: Take xor of all the elements. The number of terms occurring even number of times get cancelled due to property of xor that a ^ a = 0 I/P = [1, 2, 3, 2, 3, 1, 3]
O/P = 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #include<iostream> using namespace std; int main(){ int arr[] = {2, 3, 3, 3, 3, 4, 2, 4, 4, 2, 4}; //{1, 2, 4, 4, 10, -8}; int n = sizeof(arr)/sizeof(arr[0]); int result = 0; for(int i = 0 ; i < n ; i++ ){ result = result ^ arr[i]; } cout << result << " is the odd time occurring element!" << endl; return 0; } |
