CareerCup

I think you can use heap and BST separately for the two problems mentioned.

1. At any point of time, if you want to know only about the element that is repeated maximum number of times, you can use a max heap. For the max heap, the key will be the frequency/count of the elements in the array and an additional field, say, value would hold the element of the array.

2. At any point of time, if you want to know the element(s) that are repeated exactly n times, we can maintain a BST. Here again, the keys will be the frequency/count of the elements seen so far and an additional field called value would hold the element of the array.

To find maximum number repeated maximum times:

#include <stdio.h>

#define SIZE 13

int boyerMoore(int arr[]) {
    int current_candidate = arr[0], counter = 0, i;
    for (i = 0; i < SIZE; ++i) {
        if (current_candidate == arr[i]) {
            ++counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        } else if (counter == 0) {
            current_candidate = arr[i];
            ++counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        } else {
            --counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        }
    }
    return current_candidate;
}

int main() {
    int numbers[SIZE] = {5,5,5,3,3,1,1,3,3,3,1,3,3};
    printf("majority: %i\n", boyerMoore(numbers));
    return 0;
}

Hi,
You can use Hash Set and Hash Map for this.
-> Initially when you are reading the data insert into hash set, if and integer is repeating insert into hash map as a key, and add count. If that integer repeats again, then increment count. (As hash set doesn't allow duplicates) .
-> Hope this should work fine. as hash set insert into O(1) time and HashMap also takes O(1) time.

static void RepeatedForMaximumTimes()
{
int intCount = 1;
int[] numberList = new int[] { 4,5, 5, 5, 3, 3, 1, 4, 4, 4, 4, 1, 3, 3};
int currentNumber = numberList[0];
int MaxRepeatedNumber = numberList[0];
int MaxRepeatedCount = 1;

for (int intA = 1; intA < numberList.Length; intA++)
{
if (currentNumber == numberList[intA])
{
intCount++;
}
else
{
if(intCount > MaxRepeatedCount)
{
MaxRepeatedNumber = currentNumber;
MaxRepeatedCount = intCount;
}

intCount = 1;

currentNumber = numberList[intA];
}
}

if (intCount > MaxRepeatedCount)
{
MaxRepeatedNumber = currentNumber;
MaxRepeatedCount = intCount;
}

Console.WriteLine("Number: " + MaxRepeatedNumber + " Repeated times:" + MaxRepeatedCount);
}

It is possible to do it on-the-fly since the array is not upper-bounded.

1. maxRepeatedVal=0;maxVal=0
2.insert values as they receive into a hash table and increment the corresponding hash entry.
3. if hash[ThisValue]>maxRepeatedVal
{
maxVal = ThisValue;
maxReaptedVal=hash[ThisValue]
}

Note: If the value if maximum of N occurrences is required, then the variable maxRepeatedVal should have a constant value viz. N

We can use max heap with every node arranged by number of occurrences of that element.
Root element will give us the element with maximum occurrences.