Boyer–Moore Majority Vote Algorithm Generalization

boyer_moore_generalization.cpp

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

struct Element {
    int value;
    int count;
};

void CountGreaterThan(int array[], int n, int k) {

    if (k <= 1) {
       return;
    }

    struct Element temp[k-1];

    for (int i=0; i<k-1; i++) {
        temp[i].count = 0;
    }

    for (int i = 0; i < n; i++) {
        int j;
        for (j=0; j<k-1; j++) {
            if (temp[j].value == array[i]) {
                 temp[j].count = temp[j].count + 1;
                 break;
            }
        }

        if (j == k-1) {
            int p;
            for (p=0; p<k-1; p++) {
                if (temp[p].count == 0) {
                    temp[p].value = array[i];
                    temp[p].count = 1;
                    break;
                }
            }

            if (p == k-1)
                for (p=0; p<k; p++) {
                    temp[p].count = temp[p].count + 1;
                }
        }
    }

    cout<<"Final Output:"<<endl;
    for (int i=0; i<k-1; i++) {
        int correct_count = 0;
        for (int j=0; j<n; j++) {
            if (array[j] == temp[i].value) {
                correct_count++;
            }
        }
        if (correct_count > n/k) {
           cout << "Number " << temp[i].value<< " with count " << correct_count << endl;
        }
    }
}

int main() {
    int input_array[] = {1, 2, 2, 2, 2, 2, 2, 2, 2, 2};
    int size = sizeof(input_array)/sizeof(int);
    int k = 2;
    CountGreaterThan(input_array,size,k);
    return 0;
}