Python Program to Find Odd Occurring Number

You can find the odd occurring number in a list using the XOR operator with result = 0; for num in arr: result ^= num, which returns the number that appears an odd number of times.

Examples

Input[1, 2, 3, 2, 3, 1, 3]

Output3

Input[4, 4, 5, 5, 5]

Output5

Input[7]

Output7

How to Think About It

To find the number that appears an odd number of times, use the XOR operation because XOR of a number with itself is zero and XOR with zero is the number itself. By XORing all numbers, pairs cancel out, leaving the odd occurring number.

Algorithm

1

Initialize a variable result to 0.

2

Loop through each number in the list.

3

XOR the result with the current number.

4

After the loop ends, result holds the odd occurring number.

5

Return or print the result.

Code

python

def find_odd_occurring(arr):
    result = 0
    for num in arr:
        result ^= num
    return result

# Example usage
arr = [1, 2, 3, 2, 3, 1, 3]
print(find_odd_occurring(arr))

Output

3

Dry Run

Let's trace the list [1, 2, 3, 2, 3, 1, 3] through the code

1

Initialize result

result = 0

2

XOR with 1

result = 0 ^ 1 = 1

3

XOR with 2

result = 1 ^ 2 = 3

4

XOR with 3

result = 3 ^ 3 = 0

5

XOR with 2

result = 0 ^ 2 = 2

6

XOR with 3

result = 2 ^ 3 = 1

7

XOR with 1

result = 1 ^ 1 = 0

8

XOR with 3

result = 0 ^ 3 = 3

Step	result after XOR
0	0
1	1
2	3
3	0
4	2
5	1
6	0
7	3

Why This Works

Step 1: XOR cancels pairs

Using ^ (XOR) cancels out numbers appearing twice because a ^ a = 0.

Step 2: XOR with zero returns number

XORing with zero keeps the number unchanged: 0 ^ a = a.

Step 3: Result is odd occurring number

After XORing all, only the odd occurring number remains because all pairs cancel out.

Alternative Approaches

Using dictionary to count occurrences

python

def find_odd_occurring_dict(arr):
    counts = {}
    for num in arr:
        counts[num] = counts.get(num, 0) + 1
    for num, count in counts.items():
        if count % 2 != 0:
            return num

arr = [1, 2, 3, 2, 3, 1, 3]
print(find_odd_occurring_dict(arr))

This method uses extra space but is easy to understand and works even if multiple numbers occur odd times.

Using collections.Counter

python

from collections import Counter

def find_odd_occurring_counter(arr):
    counts = Counter(arr)
    for num, count in counts.items():
        if count % 2 != 0:
            return num

arr = [4, 4, 5, 5, 5]
print(find_odd_occurring_counter(arr))

This uses Python's built-in Counter for cleaner code but still uses extra memory.

Complexity: O(n) time, O(1) space

Time Complexity

The XOR approach loops through the list once, so it runs in linear time O(n).

Space Complexity

It uses only a single variable for XOR, so space complexity is constant O(1).

Which Approach is Fastest?

XOR is fastest and most memory efficient compared to counting methods that use extra space.

Approach	Time	Space	Best For
XOR Operator	O(n)	O(1)	Single odd occurring number, memory efficient
Dictionary Counting	O(n)	O(n)	Multiple odd occurrences, easy to understand
collections.Counter	O(n)	O(n)	Cleaner code with built-in tools