### Finding the Odd Occurrences of a Number

### Lab3.1 Finding the Odd Number of Occurrence

You are given a sorted list of numbers where one number appears odd number of times. All other numbers appear even number of times. You are required to design an efficient algorithm to find the number that appears odd number of times. I'm using the Use Divide and Conquer method which runs at $\Theta(\log(n))$

As an example, if the sorted list is

[1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6] then the odd occurrence number is 2

As an example, if the sorted list is

[1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6] then the odd occurrence number is 2

L1 = [1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7] def FindOddNumber(L): length = len(L); # If the length of L is 0, return nothing if (length == 0): return # If length of L is 1, then that's the odd occurence if (length == 1): return L[0] # Find the mid index mid_index = length / 2 # Initiate index counters to count left and right l_counter = 0 r_counter = 0 # Count occurences of the mid element to right until # the end is reached while ((L[mid_index] == L[mid_index + (r_counter + 1)])): r_counter = r_counter + 1; # If the indexes are outbound, break it if ((mid_index + (r_counter + 1)) > (length - 1)): break # Count occurences of the mid element to left until # the begining is reached while ((L[mid_index] == L[mid_index - (l_counter + 1)])): l_counter = l_counter + 1; # If the indexes are outbound, break it if ((mid_index - (l_counter + 1)) < 0): break # Deduct one to further decisions counter = r_counter + l_counter # If counter is odd, then that is not the odd occurence if (counter % 2) != 0: # If right count is odd, there are even number of # elements in the right side. That means that side # doesn't contain the odd occurence LL = L[(mid_index + r_counter + 1):] # If left count is odd, there are even number of # elements in the left side. That means that side # doesn't contain the odd occurence LR = L[:(mid_index - l_counter)] # List with odd number of elements have the odd # occurence if (len(LL) % 2 == 0): return FindOddNumber(LR) else: return FindOddNumber(LL) # Else that is the odd occurence else: return str(L[mid_index]) print FindOddNumber(L1)

## Comments

## Post a Comment