## Thursday, May 11, 2017

### Problem Statement

Given an array of size n, find the majority element. The majority element is the element that appears more than `⌊ n/2 ⌋` times.
You may assume that the array is non-empty and the majority element always exist in the array.
```       I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE```

O(n) time O(1) space fastest solution

note: Since we are assuming that majority element always exist we do not have to check for more than n/2 times more.

### Solution

• Take the first element as the majority element
• Check if the next element is equal to majority element. If  yes then increment or decrement the counter
• Note: If the counter is 0 then we need to reset it to 1
```package Algorithms.Arrays;
/*
*        I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE
*/

public class MajorityElement {

public static int get(int [] arr)
{
//We are taking the first element of the array
int major=arr[0], count=1;

for(int i=1;i<arr.length;i++)
{
//If count is set to zero during iteration we need ```
```   // to reset the count
if (count==0)
{
count++;
major=arr[i];
}
//If current element is same as major then increment the count
else if(major==arr[i])
{
count++;
}
//If we are here than we know that the current element ```
```   //is not the same then we would decrement the count
else
{
count--;
}

}
return major;

}

}
```