How to find two numbers with odd occurrences in an array

We are given an unsorted array that contains an even number of occurrences for all numbers except two. Find the two numbers which have odd occurrences.

Example

Let's consider an example of the given array and the expected output.

Example

Solution

We can solve this problem with two different methods.

Method 1

A simple technique to solve this problem is to make two nested loops. The outer loop selects an element, and the inner loop counts the number of occurrences of the selected element. If the count of occurrences is odd, then print the number. The time complexity of this technique is O(n2)O(n^2).

def CountFrequency(my_list): #function to count frequencies
odd=[] #to store odd occurence
j=1 #loop variable
for i in range(len(my_list)): #outer loop
count=0 #to keep track of occurenced
for j in range(len(my_list)): #outer loop
if my_list[i]==my_list[j]:
count=count+1
if(count%2!=0): #checking odd occurences
if my_list[i] not in odd: # not store duplicate elements
odd.append(my_list[i]) #adding into list
print(odd[:2])
#driver code
my_list = [4, 2, 4, 5, 2, 3, 3, 1]
CountFrequency(my_list)

Code explanation

Lines 1–5: We define the CountFrequency() function to check odd occurrences. We create an outer for loop.

Lines 6–8: We create an inner loop in which if statement checks the first element with all other elements of the array. When it matches, it increments the value of count .

Lines 9–12: The If condition checks count is odd or not. If yes, then appends it in odd and prints the first two odd occurrences on screen.

Method 2

We can also use a dictionary to solve this problem. First of all, create an empty dictionary that will have elements and their counts. Pick all elements of the input array one by one. Look for the picked element in the dictionary. If the element is found in an array, increment its count in the table. If the element is not found, enter it in the dictionary with a count of 1.

As elements are entered into the dictionary, scan the dictionary, and print the first two elements with the odd count. This approach may take O(n)O(n) time on average but requires O(n)O(n) extra space.

def CountFrequency(my_list):
# Creating an empty dictionary
freq = {}
for items in my_list:
freq[items] = my_list.count(items) #counting no of occurences
count=0
for key, value in freq.items(): #check odd occurences
if value%2 !=0:
count=count+1
if(count==3):
break
print(key)
#driver code
my_list = [4, 2, 4, 5, 2, 3, 3, 1]
CountFrequency(my_list)

Code explanation

Lines 1–5: We define the function CountFrequency() to check odd occurrences. We create for loop to count the number of occurrences of each element.

Lines 7–9: We make for a loop to check the odd occurrences and print the first two odd occurrences on screen when it satisfies the condition.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved