Majority Element Python

Question

I'm having trouble getting the right output on my "Majority Element" divide and conquer algorithm implementation in Python 3.

This should be relatively correct; however, it would still appear that I'm missing something or it is slightly off and I cannot figure out why that is.

I've tried some debugging statement and different things. It looks like on the particular case listed in the comment above the code, it's resolving -1 for "left_m" and 941795895 for "right_m" when it does the recursive calls. When it compares the element at each index to those variables, the counter will obviously never increment.

Am I going about this the wrong way? Any help would be greatly appreciated.

Thanks.

# Input:
# 10
# 2 124554847 2 941795895 2 2 2 2 792755190 756617003
# Your output:
# 0
# 
# Correct output:
# 1

def get_majority_element(a, left, right):
 if left == right:
     return -1
 if left + 1 == right:
     return a[left]

 left_m = get_majority_element(a, left, (left + right - 1)//2)
 right_m = get_majority_element(a, (left + right - 1)//2 + 1, right)

 left_count = 0
 for i in range(0, right):
     if a[i] == left_m:
         left_count += 1
 if left_count > len(a)//2:
     return left_m

 right_count = 0
 for i in range(0, right):
     if a[i] == right_m:
         right_count += 1
 if right_count > len(a)//2:
     return right_m

 return -1

if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))
    if get_majority_element(a, 0, n) != -1:
        print(1)
    else:
        print(0)

Answer 1

When counting the appearance of left and right major elements, your loops go over the range(0, right). Instead, they should be going over the range(left, right). Starting from 0 may, and will cause returning incorrect major elements in the smaller subproblems.

Also, in addition to the problem of having incorrect starting indices in ranges your for loops cover, you seem to have a problem in your recursive call arguments, probably due to your intuition causing you to overlook some details. Throughout the get_majority_element function, you treat parameter right to be the first index that is not in the list, as opposed to right being the index of the rightmost element in the list.

However, in your first recursive call, you give the third argument as if it is the last element included in that list. If right is the index of the first element not in that list, it should actually be the same with the second parameter of the second recursive call you're making in the following line. So, the third argument of the first recursive call you're making is less than it should be, by 1, causing you to overlook 1 element each time you recursively go down.

Thirdly, you have an error in the if statements following the for loops, similar to the problem you had with loop ranges. You are dividing the occurances of the element for all len(a) elements, although you should only care about the subproblem you are currently working on. So, you should divide it by the number of elements in that subproblem, rather than len(a). (i.e. (right - left)//2)

You can find the working code below, and look here in order to observe it's execution.

def get_majority_element(a, left, right):
    if left == right:
        return -1
    if left + 1 == right:
        return a[left]

    left_m = get_majority_element(a, left, (left + right - 1)//2 + 1)
    right_m = get_majority_element(a, (left + right - 1)//2 + 1, right)
    left_count = 0
    for i in range(left, right):
        if a[i] == left_m:
            left_count += 1
    if left_count > (right-left)//2:
        return left_m

    right_count = 0
    for i in range(left, right):
        if a[i] == right_m:
            right_count += 1
    if right_count > (right-left)//2:
        return right_m

    return -1

if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))
    print("n=" + str(n))
    if get_majority_element(a, 0, len(a)) != -1:
        print(1)
    else:
        print(0)