Find the number occuring odd number of times in an array.

Question: 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 and constant space.

Input:- arr[] = {1, 2, 3, 2, 3, 1, 3}
Output:- 3

This is a very simple problem. The basic and naive approach will be to scan the complete array and keep a track of each element. We need to count the occurrence of each element and see if its even or odd. This would be a very hectic problem. We can utilize the property of bit-wise XOR operator to make an easy solution.

A XOR A = 0 (zero)

So we can make a solution as:-

#include<stdio.h>

int main(void)
{
	//an array of 7 elements
	int arr[] = {1, 2, 3, 2, 3, 1, 3};

	int i = 0;
	int x = arr[0];

	//iterate through the array
	for(i = 1; i<7 ; i++)
	{
		// do a bit-wise XOR of all the elements
		x = x ^ arr[i];
	}

	// all the even elements are converted to 0, only the odd one remains
	printf("The number occurring odd number of times is = %d", x);

	return 0;
}

Time Complexity:- O(n)
Space Complexity:- O(1)