Given an array of positive integers. All numbers occur even a number of times except one number which occurs an odd number of times. We have to find the number occurring an odd number of times in an array.

## Example

**Input**

1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6

**Output**

4

**Approach 1 for Number Occurring Odd Number of Times**

We use the concept of XOR operation to find the number occurring an odd number of times in an array.

As we know,

**A xor A = 0** ————- **Property 1**

i.e. xor of two similar elements is zero.

Also,

**A xor 0 = A** —————**Property 2**

i.e. xor of any element with zero gives the same number.

So our algorithm will be,

**Algorithm**

1.Start from first element and loop through till the last element of an array. Perform XOR of all elements on an array.

2.XOR from point #1 will be Zero if the number occurs EVEN number of times [by property 1]

3.XOR from point#1 will be equal to the number if it is occurring an odd number of times [by property 2]

**C++ Program**

#include <bits/stdc++.h> using namespace std; int main() { int arr[]= {1,1,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,9,9}; int size = sizeof(arr)/sizeof(arr[0]); //initialize the value as first element int val = arr[0]; for(int i=1;i<size;i++) { //XOR of each element so that we can find the number occurring odd number of times val = val^arr[i]; } cout<<val<<endl; return 0; }

4

### Complexity Analysis for Number Occurring Odd Number of Times

Time Complexity: **O(N)**

Space Complexity: **O(1)**

**Approach 2 for Number Occurring Odd Number of Times **

Add the elements of an array in a Hash or Map.

**Algorithm**

1. Add the values in Hash or Map

2. Make an array element as **key** and the count of elements occurrence as the **value** of the key.

3. After adding all elements of an array, scan the map’s **value** and wherever we get a number with the odd count, then that **key** is the answer.

**C++ Program **

#include <bits/stdc++.h> using namespace std; //map to store 2 int values where first one is for the array element and second one for its count map<int,int> M; map<int,int>::iterator it; int main() { int arr[]= {1,1,2,2,4,3,2,2,3}; int size = sizeof(arr)/sizeof(arr[0]); for(int i=0;i<size;i++) { it = M.find(arr[i]); // if the number is not present in the map then add it by making its count as 1 if(it == M.end()) { M.insert(make_pair(arr[i],1)); } else //if the number is present then simply increase its count by 1 { pair<int,int> p = *it; M.erase(it); //p.second+1 is done for increasing the count by 1 M.insert(make_pair(p.first,p.second+1)); } } for(it = M.begin(); it != M.end(); it++) { //check for odd as if remainder is 1 then if evaluates to true if((it->second) % 2 ) { cout<<it->first<<endl; return 0; } } return 0; }

4

### Complexity Analysis for Number Occurring Odd Number of Times

Time Complexity: **O(N)**

Space Complexity: **O(N)**

**Approach 3 for Number Occurring Odd Number of Times**

Last and the most easily thinkable solution is to BRUTE FORCE the entire array.

**Algorithm**

1. Take an element from the array.

2. Run a loop from the start of array till end and keep on increasing the count whenever we encounter the taken element in point #1.

3. If the count in point#2 is odd then we get the answer or else continue the scan for next elements of an array.

**C++ Program **

#include <bits/stdc++.h> using namespace std; int main() { int arr[]= {5,2,1,4,3,2,3,4,3,5,1}; int size = sizeof(arr)/sizeof(arr[0]); //select each element as reference for(int i=0;i<size;i++) { int count_of_element = 0; for(int j=0;j<size;j++) { //if the number is same as the reference number if(arr[j] == arr[i]) count_of_element++; } //check for odd as if remainder is 1 then if evaluates to true if(count_of_element % 2) { cout << arr[i] <<endl; return 0; } } return 0; }

3

### Complexity Analysis for Number Occurring Odd Number of Times

Time Complexity: **O(N*N)**

Space Complexity: **O(1)**