**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.

## No comments:

## Post a Comment