Majority_Element_Divide_n_Conquer

majorit_element.cpp

/*

Author: @karngyan
Team: BlundersPride

*/

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using vll = std::vector< ll >;
using pll = std::pair< ll, ll >;
using vvll = std::vector<vll>;
using vpll = std::vector< pll >;

#define ar array
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define rep(i, begin, end) for(__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define rrep(i,a,b) for(ll i=a;i>b;--i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define cntll(a) __builtin_popcountll((a))
#define ff first
#define ss second
#define mk make_pair

const ll mod = 1e9+7;
const ll inf = 1e9;

ll go(vll &a, ll lo, ll hi) {

  if (lo == hi) {
    return a[lo];
  }

  ll mid = (lo + hi) / 2;
  ll left = go(a, lo, mid);
  ll right = go(a, mid + 1, hi);

  if (left == right) return left;

  ll lc = 0, rc = 0;
  for (int i = lo ; i <= hi ; ++i) {
    lc += (a[i] == left);
    rc += (a[i] == right);
  }

  if (lc > rc) return left;
  return right;
}


void solve(vll &a) {
  ll n = a.size();

  ll ans = go(a, 0, n - 1);

  ll cnt = 0;
  for (auto it: a) {
    cnt += (it == ans);
  }

  ans = cnt > (n/2);
  cout << ans;
}

signed main()
{

  ios_base::sync_with_stdio(false), cin.tie(nullptr);

  ll n;
  cin >> n;
  vll a(n);
  for (auto &it: a) {
    cin >> it;
  }

  solve(a);

  return 0;
}