Python Program to Find the Odd Occurring Element in an Array/list

Are you new to the java programming language? We recommend you to ace up your practice session with these Basic Java Programs Examples

Given a list which contains all duplicate elements (each element occurs even times) except one element we have to find the odd occurring element.

Given a array/list the task is to print the odd occurring element in the given list.

Examples:

Example1:

Input:

given list = [  3 , 5, 4 ,1 ,4 ,8 ,5 , 1 ,3]

Output:

The odd occurring number in the given list 8

Example2:

Input:

given list = [ 1 , 4 ,2 ,4 ,1]

Output:

The odd occurring number in the given list 2

Program to Find the Odd Occurring Element in an Array/list in Python

There are several ways to find the odd occurring element in an array .

The first thought is to run two loops and use the count to determine the frequency of the items.

If the count is one, the element is the odd one out in the specified array/list.

But this approach takes two loops. This approach therefore requires O(n^2) time complexity.

This program is therefore not an efficient way.

We will look at the efficient approaches below.

Using Hashing
Using XOR(Bitwise Operator)

Drive into Python Programming Examples and explore more instances related to python concepts so that you can become proficient in generating programs in Python Programming Language.

Method #1:Using Hashing

We can use hashing to solve this problem in O(n) time for an input containing elements. We start by traversing the array and keeping track of the frequency of each entry in a hash table. Then, after processing each array element, return the element with the odd frequency. The drawback with this strategy is that it also need O(n) more space. It also necessitates one array traverse and one hash table traversal.

Approach:

We use the Counter function to count the frequency of all entries in the given list, and it returns a dictionary with the elements as keys and the frequency as values.
Traverse the frequency dictionary and check the values of every key in it.
If the value is 1 then print the element because it is odd occurring element in the given list
Break the loop.

Below is the implementation:

# importing counter from collections
from collections import Counter
# function which returns the odd occuring element in the given list


def findOddNumb(given_list):
    # Calculating the frequency of all elements using Counter() function
    frequency = Counter(given_list)
    # Traversing the frequency dictionary
    for key in frequency:
        # checking the value if it is 1
        if(frequency[key] == 1):
            # return the element
            return key


# Driver code
# given list
given_list = [3, 5, 4, 1, 4, 8, 5, 1, 3]
# passing the given list to findOddNumb  to print the odd occuring number

print("The odd occuring number in the given list", findOddNumb(given_list))

Output:

The odd occurring number in the given list 8

Complexity analysis of the above approach :

Time Complexity : O( n)

Since hashing requires max of O(n) Time Complexity

Space Complexity : O(n)

Since it requires extra space

Method #2:Using XOR(Bitwise Operator)

We can solve this problem during a single traversal of the array and constant space. The idea is to use the XOR operator. We know that if we XOR of a number with itself an odd number of times, the result’s the amount itself; otherwise, if we XOR of a number a even number of times with itself, the result’s 0. Also, the XOR of a number with 0 is usually the amount itself.

So, if we take XOR of all array elements, even appearing elements will cancel each other, and we are left with the only odd appearing element.

Below is the implementation:

# importing counter from collections
from collections import Counter
# function which returns the odd occuring element in the given list


def findOddNumb(given_list):
    # Taking a variable xorEle and initialize it with 0
    xorEle = 0
    # Traversing the given list
    for ele in given_list:
        xorEle = xorEle ^ ele

    # return the odd occuring element
    return xorEle


# Driver code
# given list
given_list = [3, 5, 4, 1, 4, 8, 5, 1, 3]
# passing the given list to findOddNumb  to print the odd occuring number

print("The odd occuring number in the given list", findOddNumb(given_list))

Output:

The odd occurring number in the given list 8

Complexity analysis of the above approach :

Time Complexity : O( n)

Since it requires only one Traversal

Space Complexity : O(1)

Since it doesn’t requires any extra space

Related Programs: