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

- Java Program to Find the Frequency of Odd and Given Numbers in the Given Matrix
- Python Program to Swap all Odd and Even Bits of a Number
- Design a Program to Count Numbers that don’t Contain 3 in Python

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

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**:

- Python Program to Find the Missing Number in an array/list
- Python Program to Move all Zeros present in an Array/List to the End
- Python Program to Find a Pair with the Given Sum in an Array
- Python Program to Find the Second Largest Number in a List
- Python Program to Sort a List of Tuples in Increasing Order by the Last Element in Each Tuple
- Python Program to Find the Sum of Elements in a List Recursively
- Python Program to Sort the List According to the Second Element in Sublist