# 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.^{2}) - 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.

- Just do a bitwise

**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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions