// Write a program that finds the most frequent value in given integer array of size N.

// Total time should be O(N log N).

using System;

using System.Diagnostics;

public class Program

{

    public static void Main()

    {   // test

        int [] a = {2,2,35,35,35,19,14,1,19,24,29,24};

        Console.Write("Most frequent value is " + mostFreq(a));

    }

    public static int mostFreq(int[] a)

    {

        int n = a.Length;

        Trace.Assert(n > 0);

        Array.Sort(a); // O(n log n)

​

        // most frequent element is now the one that

        // forms longest continuous segment of equal elements

        // inductive extenstion:

        int lastElement = a[0]; // last element processed so far

        int lastCount = 1;      // number of occurences of lastElement

        int maxCount = 1;       // maximum length of the segment of equal elements

        int elemWithMaxCount = lastElement; // element that forms maximum length segment

        // invariant: inductive extension holds for a[0..i-1] and i<=n

        for (int i = 1; i < n; i++)

        {

            if(a[i] == lastElement)

            {

                lastCount++;

                if(lastCount > maxCount)

                {

                    maxCount = lastCount;

                    elemWithMaxCount = lastElement;

                }

            }

            else

            {

                lastCount = 1;

                lastElement = a[i];

            }

        }

        // elemWithMaxCount is the most frequent element in a[0..n-1] where n == a.Length

        return elemWithMaxCount;

    }

}