 # Two best solution's

#1

first method uses the power of probability
since it is already mentioned in question that majority element is already present , then what is the probbility of choosing the a element at random to be a majority element , 1/2 exactly so is the same for no to be a majority element but if we increase our number of trial’s then our probability of getting a majrity element in one of our trial is very high , you can mathematically proove that tobe 99.99 percent sure of getting majority element we need only 15 trials , a goof thing about this technique is that you can generalise it to n/ k majority element you just need to find the number of trial required which is very bery easy

here is the code for this technioque

int Solution::majorityElement(const vector &A) {

``````int N = A.size();

int mji = 0 ; int cnt = 1 ;

for( int i = 0 ; i < 15 ; i++ )
{
int in = rand()%N ;

int c = 0 ;
for( auto x : A )
{
if( x == A[in] )c++ ;

if( 2*c >= N  )return A[in];
}
}
``````

}

////////////////////////////////////////////

second technique is moor’s vooting algorithm which is pretty much standered algorithm every on knows that .

here is the code for it

int Solution::majorityElement(const vector &A) {

``````int N = A.size();

int mji = 0 ; int cnt = 1 ;

for( int i = 1 ; i < N ; i++ )
{
if( A[mji] == A[i] )cnt++ ;
else cnt--;

if( cnt == 0 )
{
mji = i ;
cnt = 1 ;
}
}

int c = 0 ;
for( auto x : A )
{
if( x = A[mji] )c++;

if( 2*c >= N )
{
return A[mji];
}
}
``````

}