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.
Let's consider an example of the given array and the expected output.
We can solve this problem with two different methods.
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
def CountFrequency(my_list): #function to count frequenciesodd=[] #to store odd occurencej=1 #loop variablefor i in range(len(my_list)): #outer loopcount=0 #to keep track of occurencedfor j in range(len(my_list)): #outer loopif my_list[i]==my_list[j]:count=count+1if(count%2!=0): #checking odd occurencesif my_list[i] not in odd: # not store duplicate elementsodd.append(my_list[i]) #adding into listprint(odd[:2])#driver codemy_list = [4, 2, 4, 5, 2, 3, 3, 1]CountFrequency(my_list)
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.
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
def CountFrequency(my_list):# Creating an empty dictionaryfreq = {}for items in my_list:freq[items] = my_list.count(items) #counting no of occurencescount=0for key, value in freq.items(): #check odd occurencesif value%2 !=0:count=count+1if(count==3):breakprint(key)#driver codemy_list = [4, 2, 4, 5, 2, 3, 3, 1]CountFrequency(my_list)
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