Dominator (a problem on the concept of Leader in Algorithms using Boyer-Moore Majority Vote Algo)

Dominator: Find an index of an array such that its value occurs at more than half of indices in the array.
    
An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that
 A[0] = 3    A[1] = 4    A[2] =  3
 A[3] = 2    A[4] = 3    A[5] = -1
 A[6] = 3    A[7] = 3

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

    def solution(A)

that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return -1 if array A does not have a dominator.

For example, given array A such that
 A[0] = 3    A[1] = 4    A[2] =  3
 A[3] = 2    A[4] = 3    A[5] = -1
 A[6] = 3    A[7] = 3

the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [0..100,000];
        each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Taking help from ChatGPT...

Our prompt looks like this:

You are a programming guide.

An array A consisting of N integers is given... 
... within the range [-2,147,483,648..2,147,483,647].

Please guide how to solve this problem step by step. 

Algo

To solve this problem, we can use the Boyer-Moore Majority Vote algorithm. The algorithm allows us to find a majority element (dominator in this case) in linear time complexity with constant space complexity.

Here's how we can solve it step by step:

1. Initialize two variables, candidate and count, where candidate will store the current candidate for the dominator and count will store the count of occurrences of the current candidate.

2. Iterate through the array A:
    If count is 0, set the current element as the candidate and set count to 1.

    If the current element is equal to the candidate, increment count by 1.

    If the current element is not equal to the candidate, decrement count by 1.

3. After iterating through the array, candidate will hold a potential dominator candidate. We need to verify if it's indeed the dominator by counting its occurrences in the array.

4. Iterate through the array again to count the occurrences of the candidate.
    If the count of occurrences of candidate is greater than half the length of the array, return the index of any occurrence of candidate.

    If no dominator is found, return -1.

Let's implement this in code:

Code


def solution(A):
    candidate = None
    count = 0
    
    # Find candidate for dominator
    for num in A:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    
    # Count occurrences of candidate
    count_candidate = A.count(candidate)
    
    # Check if candidate is the dominator
    if count_candidate > len(A) // 2:
        return A.index(candidate)
    else:
        return -1

# Example usage
A = [3, 4, 3, 2, 3, -1, 3, 3]
print(solution(A))  # Output should be 0, 2, 4, 6, or 7

Tags: Algorithms,Technology,