Find Odd Occurring Element

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.