Home » Algorithms

Find the number occurring an odd number of times

In this article, we are going to learn how to find the number occurring an odd number of times?
Submitted by Radib Kar, on October 30, 2018

Problem statement

Given an array of positive numbers where all the numbers occur even number of times except only one number which occurs an odd number of times. We need to find the special number (number occurring an odd number of times in the array) using minimum time complexity and space.

Solution

There’s, of course, a brute force solution existing where you can just take each element and scan the rest of the array for finding an odd number of occurrence. But such brute force solution is not acceptable since it needs O(n²) time complexity.
Hashtable can be considered as another technique for such problems. We can simply keep the counter for each element entered to the hash table and the element with an odd counter is the special element to be found. Though the time complexity is O(n), the creation of hashtable needs additional space.
Needless to say, the hash table could have been taken as our efficient solution for this problem since lower time complexity. But there exists even simple and efficient solution which can be done by bitwise XORing operation. The algorithm is very simple:
- Just do a bitwise XOR operation for all the elements and the output will be the special number which has an odd number of occurrence.
- What is most important is the reasoning behind such a tricky algorithm. A XOR A=0
  Thus the elements occurring for even number of times eventually outputs a 0. It’s only the special number which is the effective output for doing bitwise XORing for all elements as it occurs for an odd number of times.

Time complexity: O(n)

Space Complexity: O(1) (constant)

C code for implementation

#include<stdio.h>
#include<stdlib.h>

int specialNo(int a[], int n){
	int x=0;

	for(int i=0;i<n;i++){
		//xoring all elements outputs the special number
		x^=a[i];
	}

	//return the special number
	return x;
}

int main(){
	int x,count=0;

	// array of positive no initialized to -1 for now
	int a[20]={-1}; 

	printf("enter positive numbers  ending with -1\n");
	scanf("%d",&x);

	// first no
	a[0]=x;           
	while(x!=-1){
		scanf("%d",&x);
		//from second no onwards
		a[count+1]=x;  
		count++;
	}

	// function to check duplicate exists or not
	printf("\nthe special number occuring odd no of times is %d\n",specialNo(a,count)); 

	return 0;
}

Output

enter positive numbers  ending with -1
1
2
3
2
4
1
4
3
5
3
5
-1

the special number occuring odd no of times is 3