Find the two numbers with odd occurrences in an unsorted array | GeeksforGeeks
Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences in O(n) time complexity and O(1) extra space.
A O(n) time and O(1) extra space solution:
Read full article from Find the two numbers with odd occurrences in an unsorted array | GeeksforGeeks
Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences in O(n) time complexity and O(1) extra space.
A O(n) time and O(1) extra space solution:
Let the two odd occurring numbers be x and y. We use bitwise XOR to get x and y. The first step is to do XOR of all elements present in array. XOR of all elements gives us XOR of x and y because of the following properties of XOR operation.
1) XOR of any number n with itself gives us 0, i.e., n ^ n = 0
2) XOR of any number n with 0 gives us n, i.e., n ^ 0 = n
3) XOR is cumulative and associative.
1) XOR of any number n with itself gives us 0, i.e., n ^ n = 0
2) XOR of any number n with 0 gives us n, i.e., n ^ 0 = n
3) XOR is cumulative and associative.
So we have XOR of x and y after the first step.
the two set bits in xor2 indicate that the corresponding bits in x and y are different. In the second step, we pick a set bit of xor2 and divide array elements in two groups. Both x and y will go to different groups. In the following code, the rightmost set bit of xor2 is picked as it is easy to get rightmost set bit of a number. If we do XOR of all those elements of array which have the corresponding bit set (or 1), then we get the first odd number. And if we do XOR of all those elements which have the corresponding bit 0, then we get the other odd occurring number. This step works because of the same properties of XOR. All the occurrences of a number will go in same set. XOR of all occurrences of a number which occur even number number of times will result in 0 in its set. And the xor of a set will be one of the odd occurring elements.
void printTwoOdd(int arr[], int size){ int xor2 = arr[0]; /* Will hold XOR of two odd occurring elements */ int set_bit_no; /* Will have only single set bit of xor2 */ int i; int n = size - 2; int x = 0, y = 0; /* Get the xor of all elements in arr[]. The xor will basically be xor of two odd occurring elements */ for(i = 1; i < size; i++) xor2 = xor2 ^ arr[i]; /* Get one set bit in the xor2. We get rightmost set bit in the following line as it is easy to get */ set_bit_no = xor2 & ~(xor2-1); /* Now divide elements in two sets: 1) The elements having the corresponding bit as 1. 2) The elements having the corresponding bit as 0. */ for(i = 0; i < size; i++) { /* XOR of first set is finally going to hold one odd occurring number x */ if(arr[i] & set_bit_no) x = x ^ arr[i]; /* XOR of second set is finally going to hold the other odd occurring number y */ else y = y ^ arr[i]; } printf("\n The two ODD elements are %d & %d ", x, y);}