fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int majorityElement(vector<int> v) {
  5.  
  6.     //size of the given array:
  7.     int n = v.size();
  8.     int cnt = 0; // count
  9.     int el; // Element
  10.  
  11.     //applying the algorithm:
  12.     for (int i = 0; i < n; i++) {
  13.         if (cnt == 0) {
  14.             cnt = 1;
  15.             el = v[i];
  16.         }
  17.         else if (el == v[i]) cnt++;
  18.         else cnt--;
  19.     }
  20.  
  21.     //checking if the stored element
  22.     // is the majority element:
  23.     int cnt1 = 0;
  24.     for (int i = 0; i < n; i++) {
  25.         if (v[i] == el) cnt1++;
  26.     }
  27.  
  28.     if (cnt1 > (n / 2)) return el;
  29.     return -1;
  30. }
  31.  
  32. int main()
  33. {
  34.     vector<int> arr = {2, 2, 1, 1, 1, 2, 2};
  35.     int ans = majorityElement(arr);
  36.     cout << "The majority element is: " << ans << endl;
  37.     return 0;
  38. }
  39.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The majority element is: 2
https://ideone.com/6y56ly
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!