# Find Odd Occurring Element

In this coding question, we find the odd-appearing element using bitwise xor. This algorithm is simple yet powerful.

## Table of Contents

This lesson will teach you about an odd-occurring element in the given input array.

## Introduction

In this question, every element appears an even number of times except for one element, which appears an odd number of times. The element that appears an odd number of times is our answer.

Let’s see how to achieve this using the XOR operator.

## Problem statement

We need to write a program to find the element repeated an odd number of times.

```
Input: {4, 3, 3, 4, 4, 4, 5, 3, 5}
Output: 3
```

## Concepts

If we take the XOR of zero and a bit, it will return that bit.

`a ^ 0 = a`

If we take the XOR of duplicate bits, it will return 0.

`a ^ a = 0`

For `n`

numbers, the same below math can be applied.

`a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b;`

For example:

`1 ^ 5 ^ 1 = (1 ^ 1) ^ 5 = 0 ^ 5 = 5;`

So, we can XOR all bits together to find the unique number.

## Solution

### Java

```
class OddOccurringElement {
private static int helper(int[] arr) {
int res = 0;
for (int value : arr) {
res ^= value;
}
return res;
}
public static void main(String[] args) {
int result = helper(new int[]{4, 3, 3, 4, 4, 4, 5, 3, 5});
System.out.println("Odd occurring element is " + result);
}
}
```

### Python

```
def OddOccurence(array):
res=0
for value in array:
res=res^value
return res
array=[4,3,3,4,4,4,5,3,5]
print("Odd occuring element is : ",str(OddOccurence(array)))
```

### JavaScript

```
const oddOccurringEl = array => {
let res = 0;
for(let value of array) {
res ^= value;
}
return res;
}
const array = [4, 3, 3, 4, 4, 4, 5, 3, 5];
console.log (`Odd occurring element is ${oddOccurringEl (array)}`);
```

### C++

```
#include <iostream>
using namespace std;
int getOddOccurrence(int array[], int length) {
int res = 0;
for (int i = 0; i < length; i++)
res ^= array[i];
return res;
}
int main() {
int ar[] = {4, 3, 3, 4, 4, 4, 5, 3, 5};
int n = sizeof(ar) / sizeof(ar[0]);
cout << "Odd occurring element is " << getOddOccurrence(ar, n);
return 0;
}
```

### TypeScript

```
export const oddOccurringEl = (array: number[]): number => {
let res: number = 0;
for (let value of array) {
res ^= value;
}
return res;
}
const array: number[] = [4, 3, 3, 4, 4, 4, 5, 3, 5];
console.log(`Odd occurring element is ${oddOccurringEl(array)}`);
```

## Complexity analysis

**Time complexity: O(n)**

`n`

is the number of elements in the array. We need to iterate over all the elements to find a single number. So, the best and worst-case time is

.*O*(*n*)

**Space complexity: O(1)**

The space complexity is

. No extra space is allocated.*O*(1)

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.