#include <algorithm>
#include <iostream>
#include <vector>
using std::vector;
int get_majority_element(vector<int> &a, int left, int right) {
int m;
int majority_left, majority_right; // majority element in either sub array
int count_right = 0, count_left = 0; // count for above
int leftt, rightt; // endpoints
if (a.size() == 1) {
return a[0];
}
else {
m = (left + right) / 2; // calculate mid point
vector<int> b_left(m);
vector<int> b_right(right - m);
// get left sub array
for (int i = 0; i < m; i++) {
b_left[i] = a[i];
}
// set new endpoints
leftt = 0;
rightt = m;
majority_left = get_majority_element(b_left, leftt, rightt);
for (int i = 0; i < right - m + 1; i++) {
b_right[i] = a.at(m + i);
}
leftt = m;
rightt = right - m + 1;
majority_right = get_majority_element(b_right, leftt, rightt);
// if there is a majority element, count its frequency
if (majority_left != -1) {
for (int i = 0; i < a.size(); i++) {
if (a[i] == majority_left)
count_left++;
}
}
if (majority_right != -1) {
for (int i = 0; i < a.size(); i++) {
if (a[i] == majority_right)
count_right++;
}
}
// if both elements in sub arrays are majority and they're different, there is no majority element
if (count_left == count_right && majority_left != majority_right) {
return -1;
}
// check if either sub array has a majority element that occurs more than n/2 times
else if (count_right > count_left && count_right > a.size() / 2) {
return majority_right;
}
else if (count_left > count_right && count_left > a.size() / 2) {
return majority_left;
}
}
return -1;
}
int get_majority_fast(vector<int> &a, int left, int right) {
std::reverse(a.begin(), a.end());
int current = 0;
int count;
for (int i = 0; i < a.size(); i++) {
current = a[i];
count = 0;
for (int j = 0; j < a.size(); j++) {
if (a[j] == current)
count++;
}
if (count > a.size() / 2)
return 1;
}
return -1;
}
int main() {
// std::cin >> n;
// vector<int> a(n);
// for (size_t i = 0; i < a.size(); ++i) {
// std::cin >> a[i];
// }
// std::cout << (get_majority_fast(a, 0, a.size()) != -1) << '\n';
while (true) {
int one, two;
int n = rand() % 100;
std::cout << n << "\n";
vector<int> a;
for (int i = 0; i < n; ++i) {
a.push_back(rand() % 100);
}
one = get_majority_element(a, 0, a.size());
two = get_majority_fast(a, 0, a.size() != -1);
if (one != two) {
std::cout << "Wrong answer: " << one << ' ' << two << "\n";
break;
}
else {
std::cout << "OK\n";
}
}
}