Pages

Codility EquiLeader

Given a vector of integers, check if there is a leader (aka dominator) in it. If so, define equi-leader as an element of such a vector that split the vector in two subsequences, each of them has the same leader. Write a function that returns the number of equi-leaders in the passed vector.

You could find this problem, and test your solution (possibly) in your preferred programming language in the Leader codility section.

Actually, if you have already solved the other problem in the codility Leader section, named Dominator, you are already very close to the solution of this one.

To better explain what the point of the problem is, codility provides a test case, here it is, in a C++11 GoogleTest version:
TEST(EquiLeader, Given)
{
    std::vector<int> input { 4, 3, 4, 4, 4, 2 };
    ASSERT_EQ(2, solution(input));
}
The number four dominates the input sequence. If we split it on the first element (index 0) we get two subsequences where four is again a leader. The same if take the third element (index 2) as a pivot. These are the only cases correctly working on these vector, so we want our function to return 2.

I have split my C++11 solution in two parts. Firstly I wrote a utility function that gets a candidate leader for the entire sequence:
int getCandidateLeader(const std::vector<int>& input)
{
    int count = 0;
    int candidate;
    for(int cur : input) // 1
    {
        if(count == 0)
        {
            count = 1;
            candidate = cur;
        }
        else
        { // 2
            count += (candidate == cur) ? 1 : -1;
        }
    }

    return count ? candidate : std::numeric_limits<int>::max(); // 3
}
1. I am still not very used to the new C++11 range based for-loop. This is a place where it helps to make the code more readable. I am looping on the entire vector, and I don't care much about the index of any of its element, I am just interested in their values.
2. This is the central idea of this algorithm. Increasing the counter, when the current element is the same that the previously detected candidate, or throw away both elements, if they are different, let us solve the problem of getting a candidate leader in linear time.
3. If no good candidate has been detected, I return a non-acceptable value.

And this is the solution to the actual problem:
int solution(std::vector<int>& input)
{
    int leader = getCandidateLeader(input);
    if(leader == std::numeric_limits<int>::max()) // 1
        return 0;

    const unsigned count = std::count(input.begin(), input.end(), leader);
    if(count < input.size() / 2) // 2
        return 0;

    int leaders = 0; // 3
    unsigned leftLeaders = 0; // 4
    for(unsigned i = 0; i < input.size(); ++i)
    {
        if(input[i] == leader) // 5
            leftLeaders++;
        unsigned rightLeaders = (count - leftLeaders); // 6
        if(leftLeaders > (i + 1) / 2 && rightLeaders > (input.size() - i - 1) / 2)
            ++leaders; // 7
    }

    return leaders;
}
1. No candidate leader found, no need to go on.
2. The candidate leader is not dominant.
3. Keep memory of the current number of equi-leaders.
4. Here I store the number of leader occurrences in the current left subsequence. In the first loop, it contains just the leftmost element. It would grow till it would get all the sequence.
5. If the current element is a leader, increase the left counter.
6. Get the right subsequence number of leaders by subtraction.
7. If both left and right leader count are dominant in their subsequence, increase the equi-leader counter.

No comments:

Post a Comment