# One Odd Occurring

Problem Statement: Given an array of positive integers, where all elements are occurring even a number of times except one which is occurring an odd number of times.

Examples:

```Example 1:
Input: arr = {1,2,3,2,3}
Output: 1
Explanation: only one element is occuring odd number of times  i.e. 1 .

Example 2:
Input: arr = {4,5,6,5,6,9,9,4,4}
Output: 4
Explanation: Only one element is occuring odd number of times  i.e. 4 .```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

### Solution 1:

Approach:

The approach is very simple where we will run two nested loops, and count the occurrence of every element. If at any moment, we are getting the count as odd, we will just print that element.

`For eg , - arr = {1 , 2 , 3 , 2 , 1}`
• The first iteration –  1 is occurring 2 times
• The second iteration – 2 is occurring 2 times
• The third iteration – 3 occurs 1 time (odd number of times).

This means the answer is ‘3’.

Code:

## C++ Code

``````#include <bits/stdc++.h>
using namespace std;
// Function to find one odd occuring element
int findoddoccuring(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (arr[i] == arr[j])
count++;
}
if (count%2!=0)
return arr[i];
}
return -1;
}
int main()
{
int n = 5;
int arr[] = {1, 2, 3, 2, 1};
cout << findoddoccuring(arr, n)<<" is occurring an odd number of times"<< endl;
return 0;
}
``````

Output: 3 is occurring an odd number of times

Time Complexity: O( n2 ), since we are using nested loop

Space Complexity: O(1)

## Java Code

``````import java.util.*;
public class Main {
// Function to find one odd occuring element
public static int findoddoccuring(int[] arr, int n) {
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j])
count++;
}
if (count%2!=0)
return arr[i];
}
return -1;
}
public static void main(String args[]) {
int n = 5;
int[] arr = {1, 2, 3, 2, 1};
System.out.println(findoddoccuring(arr, n)+" is occurring an odd number of
times");
}
}
``````

Output: 3 is occurring an odd number of times

Time Complexity: O( n2 ), since we are using nested loop

Space Complexity: O(1)

### Solution 2:

Approach:

Approach 2 is also simple where we will use hash data structure So here we will be using extra auxiliary space of O(n). Here we will count occurrences of every element.

(Note that – hash stores distinct elements and it stores key, value pair )

`For eg , - arr = {1 , 2 , 3 , 2 , 1}`

Creating a hash map

```Element       occurrences
1        |        2
2        |        2
3        |        1
```

Since occurrences of ‘3’ are 1 . So it is the odd occurring element.

Code:

## C++ Code

``````#include <bits/stdc++.h>
using namespace std;
// Function to find one odd occuring element using hashing
int findoddoccuring(int arr[], int n)
{
map<int, int> mp;
for (int i = 0; i < n; i++)
{
mp[arr[i]]++;
}
for (auto it : mp)
{
if (it.second % 2 != 0)
return it.first;
}
return -1;
}
int main()
{
int n = 5;
int arr[] = {1, 2, 3, 2, 1};
cout<<findoddoccuring(arr, n)<<" is occurring an odd number of times"<<endl;
return 0;
}
``````

Output: 3 is occurring an odd number of times

Time Complexity: O(n), where n is the size of the array

Space Complexity: O(n), auxiliary space required for hash data structure

## Java Code

``````import java.util.*;
public class Main {
// Function to find one odd occuring element using hashing
public static int findoddoccuring(int[] arr, int n) {
HashMap < Integer, Integer > mp = new HashMap < > ();
for (int i = 0; i < n; i++) {
if (mp.containsKey(arr[i]))
// mp.get(arr[i]) - gives us previous count
// increment it by 1
// and put in the map again
mp.put(arr[i], mp.get(arr[i]) + 1);

else
mp.put(arr[i], 1);

}
for (Integer it: mp.keySet()) {
if (mp.get(it) % 2 != 0)
return it;
}
return -1;
}
public static void main(String args[]) {
int n = 5;
int[] arr = {1, 2, 3, 2, 1};
System.out.println(findoddoccuring(arr, n)+" is occurring an odd number of
times");
}
}
``````

Output: 3 is occurring an odd number of times

Time Complexity: O(n), where n is the size of the array

Space Complexity: O(n), auxiliary space required for hash data structure

### Solution 3 :

Approach:

The Best approach is bitwise Xor all elements of the array where even occurring elements on xor will give 0 whereas odd occurring element on xor give us the number since its even occurrence will give 0.

`For Eg - arr = {7,2,3,3,2,7,7}`

^ represents xor Code:

## C++ Code

``````#include <bits/stdc++.h>
using namespace std;
// Function to find one odd occuring element using xor
int findoddoccuring(int arr[], int n)
{
int xorele = 0;
for (int i = 0; i < n; i++)
xorele = xorele ^ arr[i];
return xorele;
}
int main()
{
int n = 5;
int arr[] = {1, 2, 3, 2, 1};
cout<<findoddoccuring(arr, n)<<" is occurring an odd number of times"<<endl;
return 0;
}
``````

Output: 3 is occurring an odd number of times

Time Complexity: O(n) for taking the xor of n elements

Space Complexity: O(1)

## Java Code

``````import java.util.*;
public class Main {
// Function to find one odd occuring element using xor
public static int findoddoccuring(int[] arr, int n) {
int xorele = 0;
for (int i = 0; i < n; i++)
xorele = xorele ^ arr[i];
return xorele;
}
public static void main(String args[]) {
int n = 5;
int[] arr = {1, 2, 3, 2, 1};
System.out.println(findoddoccuring(arr, n)+" is occurring an odd number of
times");
}
}
``````

Output: 3 is occurring an odd number of times

Time Complexity: O(n) for taking the xor of n elements

Space Complexity: O(1)