# Find Majority Element in an Array

Majority element in an array Array[] of size n is an element that appears more than n/2 times.

Write a function which takes an array and gives the majority element (if it exists), otherwise return -1.

Example:

Input : 2 4 5 5 5 0

Result : 5

Input : 3 5 6 9 6 7

Result : -1

Method 1: (n2 run time)

The basic solution is to have two loops and keep track of count for current element. If the count becomes greater than n/2 then break the loops and return the element. If loop ends completely then simply return -1.

Time Complexity: O(n*n).

Auxiliary Space : O(1).

**Method 2: **

1. Sort the Array.

2. Start from middle element and count on both way if left or right element is equal to middle element.

If the count is greater than n/2 then break and return the element.

* Logic: If any number exist more than n/2 time, it will must come in middle of sorted array.*

Time Complexity: O(n*logn) [ Based on sorting algorithm]

Auxiliary Space : O(1).