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


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

Popular posts from this blog

Python Laboratory Excersices

DDR3 vs. DDR3L RAM

Installing TOMCAT