0
$\begingroup$

I'm trying to solve the problem for finding majority element of given array. I made two attempts to solve the problem, but seems that both have something wrong in them. First one relies on the logic that : 1) If $A$ is array with $n$ elements then $A$ has majority element $\Leftrightarrow A_{1} = A[1,...,\frac{n}{2}], A_{2} = A[\frac{n}{2} + 1, ...,n]$ both $A_{1}$ and $A_{2}$ have a majority element and the majority element of the first is equal of the majority element of the second subarray. The bottom of the recursive definition is when $A.size = 1$ then every singleton has a majority element - the only element itself.

Here is an implementation in C++ :

#include <vector>
#include <iostream>
#include <limits.h>
#define INF INT_MAX

int majority(std::vector<int>& arr, int begin, int end)
{
    if(begin == end)
        return arr[begin];
    int mid = (begin + end) / 2;
    int majorityLeft = majority(arr, begin, mid);
    int majorityRight = majority(arr, mid + 1, end);
    if(majorityLeft == majorityRight)
        return majorityLeft;
    else if(majorityLeft != majorityRight && 
            majorityLeft != INF &&
            majorityRight != INF)
        return INF;
    else if(majorityLeft != INF || majorityRight != INF)
        return std::min(majorityLeft, majorityRight);
    else return INF;
}

The second attempt relies on the Dirichlet principle. If i randomly divide the arry into $\frac{n}{2}$ pairs then at least one pair is going to satisfy the condition $\exists i,j : i \neq j, i < j \le n : A[i] = A[j]$ Then for every pair if the elements are equal i keep just one of them in new array, and if they are not equal i discard both of them. Then recussively do the same on the new array.

Here is C++ implementation :

int majority2(std::vector<int>& arr)
{
    if(arr.size() == 1)
        return arr[0];
    if(arr.size() == 0)
        return INF;
    std::vector<int> subArr;
    for(int i = 1 ; i < arr.size() ; i += 2){
        if(arr[i - 1] == arr[i])
            subArr.push_back(arr[i - 1]);
    }
    if(arr.size() % 2 == 1)
        subArr.push_back(arr[arr.size() - 1]);
    return majority2(subArr);
}

I'll be really grateful if somebody tells me what is my mistake in the implementation or algorithms' logic!

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "majority element"? $\endgroup$ – fade2black Jul 20 '17 at 15:19
  • $\begingroup$ If there is array $A$ with n elements, we call x major if at least $\frac{n}{2}$ elements are equal to x $\endgroup$ – Zarrie Jul 20 '17 at 15:37
  • $\begingroup$ I tried your first algorithm with the following input vector<int> a = {1,2,4,5,5,5}; which returns INF. But by your definition it should return 5 since there are at least 3 fives. $\endgroup$ – fade2black Jul 20 '17 at 16:07
  • 1
    $\begingroup$ You should explain your solution without using a specific programming language. Don't expect all people will understand C++ or Ruby or Python. It is not clear whether your mistake is in logic or programming. $\endgroup$ – fade2black Jul 20 '17 at 16:10
  • $\begingroup$ Finding the bug in your C++ code is probably off-topic here. However, the linked question describes a valid algorithm. Also, in the future, please don't respond to questions by leaving clarifications in the comments. Instead, edit the question to add any missing information, so people don't have to read the comments to understand what you're asking. $\endgroup$ – D.W. Jul 20 '17 at 16:27