====== عنصر غالب ======
این سؤال یکی از جالب‌ترین سؤال های قابل حل با روش استقرایی است که در زیر به بررسی آن در زمان 
$O(n)$
می‌پردازیم.

===== تعریف =====
آرایه‌ای شامل $n$ عضو داریم. می‌خواهیم عنصری را در آن پیدا کنیم که بیش از $\frac{n}{2}$ بار تکرار شده است.

===== الگوریتم =====
دو مقدار $x, occ$ را به صورت زیر تعریف کنید: \\
$x$:
عنصری که شانس تکرار بیش از مقدار مورد نظر را داشته باشد. \\
$occ$:
اگر $T$ را برابر با تعداد تکرار‌های $x$ در آرایه در نظر بگیرید، اگر 
$T \leq \frac{n}{2}$
بود،‌ آن‌گاه 
$occ \leq T$
است. در غیر این صورت‌ 
$occ = n - T$
می‌باشد. \\
حال در صورتی که مقدیر $x, occ$ را در هر مرحله، با حذف عضو $n$ ام، و اضافه کردن آن، به صورت استقرایی انجام دهیم، واضح است که اگر عنصری شرایط ما را برآورده کرده باشد، همان عنصر $x$ خواهد بود. پس کافی است که فقط بررسی کنیم که آیا عنصر $x$ بیش از مقدار مورد نظر ما در آرایه آمده است یا خیر.
===== پیچیدگی‌ الگوریتم =====
پیچیدگی این الگوریتم به وضوح از 
$O(n)$
است.

===== پیاده‌سازی =====

<code cpp dominant_element.cpp>
#include <iostream>
using namespace std;
const int maxn = 1000 * 1000 + 10;
int a[maxn];
int main() {
     int n;
     cin >> n;
     for(int i=0;i<n;++i)
         cin >> a[i];
     
     int x = a[0];
     int occ = 1;
     for(int i=1;i<n;++i)
         if(x == a[i])
             occ++;
         else{
             occ--;
             if(occ < 0) {
                 occ = 1;
                 x = a[i];
             }
         }
  
     int T = 0;
     for(int i=0;i<n;++i)
         if(x == a[i])
             T++;
  
     if(T > n / 2)
        cout << "We find it!! The element is: " << x << endl;
     else
        cout << "There is no dominant element :(" << endl;
  
     return 0;
}


</code>