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.

ggorantala
ggorantala
2 min read

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

Coding Interview QuestionsData Structures and AlgorithmsArraysBit Manipulation

ggorantala Twitter

Gopi has a decade of experience with a deep understanding of Java, Microservices, and React. He worked in India & Europe for startups, the EU government, and tech giants.

Comments


Related Posts

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!

Members Public

Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things

Members Public

Find Even Number Of Digits in an Array

This problem tests your knowledge of mathematics. Solving this problem helps you find the place values and how they are represented in the decimal number system.