Find element which occur ODD time in an array using O(n) time and O(1) space in C

Given an array with n elements, all the elements occur even times except one element Write a C++/C program to find out that one element in O(n) time and using O(1) space.

It can be done with the help of Bitwise XOR (^) Operator i.e. all elements occur even times so on performing XOR operation.

They will give result as 0 and at last only the element that occurs odd times will be left and that will be the result.

As, a^a = 0 and a^0 = a.

For example : Given an array is 2,3,2,4,3,5,6,6,5.
In this array 4 occurs odd times only. So, 4 should be the output.

Consider the program

#include <stdio.h>

int main()
{
	int arr[] = {2,3,2,4,3,5,6,6,5};
	int n = sizeof(arr) / sizeof(arr[0]);

	int xor_result = 0;
	for( int i=0; i<n ;i++)
		xor_result = xor_result ^ arr[i];

	printf("%d is an element that occurs odd number of times.\n",xor_result);

	return 0;	
}

output

4 is an element that occurs odd number of times.

Find element which occur ODD time in an array using O(n) time and O(1) space in C

COMMENTS