How to solve this corner case in the implementation of the algorithm for finding the majority element through divide-and-conquer?

Question

Algorithms

Problem: I want to write an algorithm that would find the majority element of an array (or find its absence). Basically, I took the algorithm from LeetCode - Approach 5. This is what my code looks like:

long long majority_element(vector<long long>& a, unsigned long long lo, unsigned long long hi) {
    if (lo == hi) return a[hi];

    auto mid = (hi - lo) / 2 + lo;
    auto left = majority_element(a, lo, mid);
    auto right = majority_element(a, mid+1, hi);

    if (left == right) return right;

    auto l_cnt = count(a.begin(), a.end(), left);
    auto r_cnt = count(a.begin(), a.end(), right);

    if (r_cnt == l_cnt) return 0; // если вернулся ноль - мажоритарного нет
    return l_cnt > r_cnt ? left : right;
}

I ran into a problem. This algorithm, as far as I understand, proceeds from the fact that "if an element is majority in both halves of the array, it is also majority in the full array". If suddenly there is a different majority element in different parts, the conflict is easily solved by recalculating the elements in the entire array in order to answer the question "Which element has more occurrences?". But, for example, let's look at this example:

512766168 717383758 5 126144732 5 573799007 5 5 5 405079772

Obviously, there is no majority element here. But the algorithm splits the original array into two parts and gets two halves - and in each half 5 is the majority element. And then, since the element is majority in both sides of the array, it is also majority in the entire array - 5 is returned, which, of course, is not true. Is it possible to somehow fix this problem without stupid count() in case the element is majority in both halves?

Answer 1

Your code is wrong - you need to count() not on the entire array, but only between low and high.
Then the complexity of the whole algorithm will be O(n log n). What you have now done will have O(n^2) complexity.
There is no way to get rid of the calculation in this solution.

Answer 2

512766168
717383758
5
126144732
5
---------------
573799007
5
5
5
405079772

in the first half, "5" will not be a majority element:
there are only 2 fives, while it should be > N/2, i.e. from 2.5 (3)

Answer 3

Is it possible to somehow fix this problem without stupid count() in case the element is majority in both halves?

remove all duplicate elements from the input, remember the element with an odd number of repetitions and with the maximum number of duplicates and the number of such duplicates.
After splitting - find this element in one of the halves. They didn’t find it in one, so it’s definitely present in the other half, because. the considered number of repeating elements is always odd.