# Majority Frequency Element

We have an array of intergers a[]. Our task is to find the majority element in the array.

A majority element in an array a[] of size n is an element that appears more than n/2 times. So there will be at most one such element.

##### Example 1

Input : a[]={3, 3, 6, 2, 6, 6, 2, 6, 6}

Output : 6

Explanation: The frequency of 6 is 5 which is greater than the half of the size of the array size.

##### Example 2

Input : a[] = {3, 3, 6, 2, 6, 6, 2, 6}

Output : No Majority Element

Explanation: There is no element whose frequency is greater than the half of the size of the array size.

#### Approach

Approach to finding the majority element in an array is to use the Boyer-Moore Majority Vote Algorithm, which is an efficient and clever algorithm that doesn't require sorting or additional data structures

- Initialize two variables: candidate and count. The candidate represents the current element under consideration as a potential majority element, and count is used to keep track of how many times the candidate has been seen so far. Initially, both are set to null or 0.
- Iterate through the array one element at a time.
- For each element in the array:
- f count is 0, set the current element as the new candidate and increment count to 1.
- If the current element is the same as the candidate, increment count by 1.
- If the current element is different from the candidate, decrement count by 1.

- After iterating through the entire array, the candidate variable will hold the element that is most likely the majority element.
- To confirm if the candidate is indeed the majority element, iterate through the array again and count the occurrences of the candidate.
- If the count of the candidate is greater than n/2 (where n is the size of the array), it is considered the majority element. Otherwise, there is no majority element in the array.

#### Complexity

- Time Complexity: O(N), where N is the number of elements in the array.
- Space Complexity: O(1), because the code uses a fixed number of variables

#### Code

```
#Java Code
public class MajorityElementFinder {
public int findMajorityElement(int[] nums) {
int candidate = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
return candidate;
}
public boolean isMajorityElement(int[] nums, int candidate) {
int count = 0;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
return count > nums.length / 2;
}
public static void main(String[] args) {
MajorityElementFinder finder = new MajorityElementFinder();
int[] arr = {3, 3, 6, 2, 6, 6, 2, 6, 6};
int majorityCandidate = finder.findMajorityElement(arr);
if (finder.isMajorityElement(arr, majorityCandidate)) {
System.out.println("The majority element is " + majorityCandidate);
} else {
System.out.println("There is no majority element in the array.");
}
}
}
```

##### Output

The majority element is 6