// Find Most Frequently Occurring Number in O(n) - 
// Algorithm works for n/2 + 1, but not for any less frequent number (ex: n/3)
//
#include <stdio.h>

//#define DEBUG_PRINT

#define SIZE_OF_ARRAY(a)   (sizeof((a))/ sizeof((a)[0]))

int FindMostFrequentNumber(int *pNumbers, int nNumbers, int skipNumber);
void PrintFrequencies(int *pNumbers, int nNumbers);

int main(int argc, char *args[])
{
  int *pNumbers;
  int nNumbers;
  int mostFrequentNumber1;
  int mostFrequentNumber2;

  // Case: At least n/2 + 1 frequency
  int nums1[12] = 
   {2, 2, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2}; // Answer: 2
  int nums2[24] = 
   {5, 5, 5, 5, 5, 5, 5, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 5, 5, 5, 5, 5, 5}; // Answer: 5
  int nums3[25] = 
   {5, 5, 5, 5, 5, 8, 8, 8, 8, 5, 5, 8, 8, 5, 5, 5, 8, 8, 8, 8, 8, 8, 5, 5, 5}; // Answer: 5

  // Case: Less than n/2 + 1 frequency
  int nums4[] = 
    {1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 8, 8, 8, 3, 3, 3, 3}; // Answer: 3
  int nums5[] = 
   {1, 2, 2, 3, 3, 4, 4, 2, 2, 5, 5, 2, 2, 6, 6, 6, 2, 2}; // Answer: 2

  // Case: At least n/3 + 1 frequency
  int nums6[18] = 
    {2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 4, 4, 4, 4};

  printf("\n");

  pNumbers = (int *) nums1; nNumbers = SIZE_OF_ARRAY(nums1);
  PrintFrequencies(pNumbers, nNumbers);
  mostFrequentNumber1 = FindMostFrequentNumber(pNumbers, nNumbers, -1);
  mostFrequentNumber2 = FindMostFrequentNumber(pNumbers, nNumbers, mostFrequentNumber1);
  printf("Most Frequent Numbers : %d, %d\n", mostFrequentNumber1, mostFrequentNumber2);

  pNumbers = (int *) nums2; nNumbers = SIZE_OF_ARRAY(nums2);
  PrintFrequencies(pNumbers, nNumbers);
  mostFrequentNumber1 = FindMostFrequentNumber(pNumbers, nNumbers, -1);
  mostFrequentNumber2 = FindMostFrequentNumber(pNumbers, nNumbers, mostFrequentNumber1);
  printf("Most Frequent Numbers : %d, %d\n", mostFrequentNumber1, mostFrequentNumber2);

  pNumbers = (int *) nums3; nNumbers = SIZE_OF_ARRAY(nums3);
  PrintFrequencies(pNumbers, nNumbers);
  mostFrequentNumber1 = FindMostFrequentNumber(pNumbers, nNumbers, -1);
  mostFrequentNumber2 = FindMostFrequentNumber(pNumbers, nNumbers, mostFrequentNumber1);
  printf("Most Frequent Numbers : %d, %d\n", mostFrequentNumber1, mostFrequentNumber2);

  pNumbers = (int *) nums4; nNumbers = SIZE_OF_ARRAY(nums4);
  PrintFrequencies(pNumbers, nNumbers);
  mostFrequentNumber1 = FindMostFrequentNumber(pNumbers, nNumbers, -1);
  mostFrequentNumber2 = FindMostFrequentNumber(pNumbers, nNumbers, mostFrequentNumber1);
  printf("Most Frequent Numbers : %d, %d\n", mostFrequentNumber1, mostFrequentNumber2);

  pNumbers = (int *) nums5; nNumbers = SIZE_OF_ARRAY(nums5);
  PrintFrequencies(pNumbers, nNumbers);
  mostFrequentNumber1 = FindMostFrequentNumber(pNumbers, nNumbers, -1);
  mostFrequentNumber2 = FindMostFrequentNumber(pNumbers, nNumbers, mostFrequentNumber1);
  printf("Most Frequent Numbers : %d, %d\n", mostFrequentNumber1, mostFrequentNumber2);

  pNumbers = (int *) nums6; nNumbers = SIZE_OF_ARRAY(nums6);
  PrintFrequencies(pNumbers, nNumbers);
  mostFrequentNumber1 = FindMostFrequentNumber(pNumbers, nNumbers, -1);
  mostFrequentNumber2 = FindMostFrequentNumber(pNumbers, nNumbers, mostFrequentNumber1);
  printf("Most Frequent Numbers : %d, %d\n", mostFrequentNumber1, mostFrequentNumber2);

  return 0;
}

int FindMostFrequentNumber(int *pNumbers, int nNumbers, int skipNumber)
{
  int i;
  int count = 0;
  int mostFrequentNum = -1;

  for (i = 0; i < nNumbers; i++)
  {
    if (-1 != skipNumber && pNumbers[i] == skipNumber)
      continue;

    if (0 == count || pNumbers[i] == mostFrequentNum)
    {
#ifdef DEBUG_PRINT
      if (0 == count)
      {
        printf("DEBUG: Flip Point [%d] = %d\n", i, pNumbers[i]); 
      }
#endif

      mostFrequentNum = pNumbers[i];
      ++count;
    }
    else
    {
      --count;
    }
  }

  return mostFrequentNum;
}

void PrintFrequencies(int *pNumbers, int nNumbers)
{
  int i, j, count, mostFrequentCount, mostFrequentNumber;

  int *pSkip = NULL;

  printf("\n");
  printf("Collection (Size = %d) : ", nNumbers);
  for (i = 0; i < nNumbers; i++)
  {
    printf("%d, ", pNumbers[i]);
  }
  printf("\n");

  printf("Frequencies (Number, Count) : ");

  pSkip = (int *) malloc(nNumbers * sizeof(int));

  if (NULL == pSkip) return;

  for (i = 0; i < nNumbers; i++)
  {
    pSkip[i] = 0;
  }

  mostFrequentNumber = -1;
  mostFrequentCount = -1;

  for (i = 0; i < nNumbers; i++)
  {
    if (1 == pSkip[i]) continue;

    count = 0;
  
    for (j = i; j < nNumbers; j++)
    {
      if (pNumbers[i] == pNumbers[j])
      {
        ++count;
        pSkip[j] = 1;
      }
    }

    printf("(%d, %d), ", pNumbers[i], count);
 
    if (mostFrequentCount < count)
    {
      mostFrequentCount = count;
      mostFrequentNumber = pNumbers[i];
    }
  }

  printf("\n");
  printf("Expected Most Frequent Pair = (%d, %d)\n", mostFrequentNumber, mostFrequentCount);

  if (NULL != pSkip) { free(pSkip); }
}

Collection (Size = 12) : 2, 2, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2, 
Frequencies (Number, Count) : (2, 7), (3, 5), 
Expected Most Frequent Pair = (2, 7)
Most Frequent Numbers : 2, 3

Collection (Size = 24) : 5, 5, 5, 5, 5, 5, 5, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 5, 5, 5, 5, 5, 5, 
Frequencies (Number, Count) : (5, 13), (8, 11), 
Expected Most Frequent Pair = (5, 13)
Most Frequent Numbers : 5, 8

Collection (Size = 25) : 5, 5, 5, 5, 5, 8, 8, 8, 8, 5, 5, 8, 8, 5, 5, 5, 8, 8, 8, 8, 8, 8, 5, 5, 5, 
Frequencies (Number, Count) : (5, 13), (8, 12), 
Expected Most Frequent Pair = (5, 13)
Most Frequent Numbers : 5, 8

Collection (Size = 18) : 1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 8, 8, 8, 3, 3, 3, 3, 
Frequencies (Number, Count) : (1, 1), (2, 1), (3, 7), (4, 1), (5, 1), (6, 1), (7, 1), (8, 5), 
Expected Most Frequent Pair = (3, 7)
Most Frequent Numbers : 8, 3

Collection (Size = 18) : 1, 2, 2, 3, 3, 4, 4, 2, 2, 5, 5, 2, 2, 6, 6, 6, 2, 2, 
Frequencies (Number, Count) : (1, 1), (2, 8), (3, 2), (4, 2), (5, 2), (6, 3), 
Expected Most Frequent Pair = (2, 8)
Most Frequent Numbers : 6, 2

Collection (Size = 18) : 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 4, 4, 4, 4, 
Frequencies (Number, Count) : (2, 7), (3, 7), (4, 4), 
Expected Most Frequent Pair = (2, 7)
Most Frequent Numbers : 4, 2