Dominator


My solution written in C++11

#include <vector>

using namespace std;

int solution(vector<int> &A) {

   int size = 0;
   int value = 0;

   auto push = [&](int item)
   {
      if ( size == 0 )
      {
         value = item;
         ++size;
      }
      else
      {
         if ( item != value )
            --size;
         else
            ++size;
      }
   };

   for ( auto i = A.cbegin(); i != A.cend(); ++i )
   {
      push(*i);
   }

   if ( size < 1 )
      return -1;

   int cnt = 0;

   for ( int i = 0; i<A.size(); ++i )
   {
      if ( value == A[i] )
         ++cnt;

      if ( cnt > A.size() / 2 )
         return i;
   }

   return -1;

}
Comments