Find the element repeated more than n/2 times

There is an array (of size N) with an element repeated more than N/2 number of time and the rest of the element in the array can also be repeated but only one element is repeated more than N/2 times. Find the number.

Approach#1

Keep the count of each number in a hash map.

Extra space required for this approach.

Approach#2

Simplest, sort the array and the number at n/2+1th index is the required number.

Time complexity to sort array is: O (nlogn).

Approach#3
Moore’s Voting Algorithm

1. Define two variables majority_elem to keep track of majority element and counter (count).

2. Initially we set the first element of the array as the majority element.

3. Traverse the array:

a. If the current element == majority_elem

Increment count

    else

Decrement count

b. If count becomes zero,

Set count = 1

Set majority_elem = current element.

4. Print majority_elem.

array = [1, 2, 3, 4, 5, 5, 5, 5, 5 ]

majority_elem = items[0]

count = 1

for i ß 0 to end {

if (items[i] == majority_elem) {

          count += 1;

            } else {

          count -= 1

            }

           if (count == 0) {

                majority_elem = items[i];

                count = 1;

            }

}

print(majority_elem)

Note:  For boundary condition, Check that the occurrence of element is more than n/2.

Intuition behind the algorithm:

Suppose that you were to have a roomful of people each holding one element of the array. Whenever two people find each other where neither is holding the same array element as the other, the two of them sit down. Eventually, at the very end, if anyone is left standing, there's a chance that they're in the majority, and you can just check that element. As long as one element occurs with frequency at least N/2, you can guarantee that this approach will always find the majority element.