CODEWITHSUNDEEP
c#algorithm
Tom H
Tom H

Reputation: 31

Computing the most frequent element

I have recently come across this line of code and what it does is that it goes through an array and returns the value that is seen most often. For example 1,1,2,1,3 so it will return 1 because it appears more than 2 and 3. What I am trying to do is understand how it works so what I did was I went through it with visual studio step by step but it is not ringing any bells.

Can anyone help me understand what is going on here? It would be a total plus if someone can tell me what does c do and what is the logic behind the arguments in the if statements.

    int[] arr = a;
    int c = 1, maxcount = 1, maxvalue = 0;
    int result = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        maxvalue = arr[i];
        for (int j = 0; j <arr.Length; j++)
        {
            if (maxvalue == arr[j] && j != i)
            {
                c++;
                if (c > maxcount)
                {
                    maxcount = c;
                    result = arr[i];
                }
            }
            else
            {
                c=1;
            }
        }
    }
    return result;

Upvotes: 1

Views: 112

Answers (2)

Atul Sikaria
Atul Sikaria

Reputation: 294

It is not computing the most frequent element - what it is computing is the longest run of elements.

Also, it is not doing it very efficiently, the inner loop only needs to compute upto i-1, not upto arr.Length.

c is keeping track of the current run length. The first "if" is to check if this is a "continouous run". The second "if" (after reaching the last element in the run) will check if this run is longer than any run you have seen so far.

In the above input sample, you are getting 1 as answer because it is the longest run. Try with an input where the element with the longest run is not the same as the most frequent element. (e.g., 2,1,1,1,3,2,3,2,3,2,3,2 - here 2 is the most frequent element, but 1,1,1 is the longest run).

Upvotes: 1

Anirudh Ramanathan
Anirudh Ramanathan

Reputation: 46768

EDIT: On closer examination, the code snippet has a nested loop and is conventionally counting the maximum seen element by simply keeping track of the maximum seen times and the element that was seen and keeping them in sync.

That looks like an implementation of the Boyer-Moore majority vote counting algorithm. They have a nice illustration here.

The logic is simple, and is to compute the majority in a single pass, taking O(n) time. Note that majority here means that more than 50% of the array must be filled with that element. If there is no majority element, you get an "incorrect" result.

Verifying if the element is actually forming a majority is done in a separate pass usually.

Upvotes: 1

Related Questions