# Find Odd Occurring Element

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

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 `O(1)`. No extra space is allocated.

Coding Interview QuestionsData Structures and AlgorithmsArraysBit Manipulation

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!