Let A[1..n] be an array with n numbers. An element x in A[1..n] is said to be cool if it appears more than n/2 times

Question

Let A[1..n] be an array with n numbers. An element x in A[1..n] is said to be cool if it appears more than n/2 times in A[1..n]. For instance, 5 is cool in [5, 1, 5, 2, 5, 2, 5], but in [1, 4, 2, 6, 5, 4, 4, 4], no element is cool. Design a O(n) time algorithm that decides whether or not there is a cool element in A[1..n]. If there is no cool element, the algorithm must return “No”. If there is a cool element, the algorithm must return the value of the cool element. Explain why your algorithm is correct and why it does take O(n) time. Note: You may use any algorithm that was presented in class as a black box (your algorithm must be deterministic). Describe your algorithm in plain English.

Answer 1

Hint 1 : if $a$ is cool in $A[1..n]$ is it possible to have $b\neq a$ cool in $A[1..n]$?

Hint 2 : if $a$ is cool in $A[1..n]$ what can you say about the coolness of $a$ in $A[1..n/2]$ and $A[n/2..n]$?

Hint 3 : if you know that $a$ is cool in $A[1..n/2]$ and $b$ is cool in $A[n/2..n]$ how hard is it to determine if A[1..n]$ has a cool element?