Skip to content

Find Odd Occurring Element

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

Gopi Gorantala
Gopi Gorantala
2 min read

Table of Contents

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


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


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.



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);


def OddOccurence(array):
    for value in array:
    return res

print("Odd occuring element is : ",str(OddOccurence(array)))


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)}`);


#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;


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 Gorantala Twitter

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.


Related Posts

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

Leetcode 217: Contains Duplicate
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,

Leetcode 121: Best Time To Buy and Sell Stock
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!