$2.$ Given an integer array A$[1..$n$],$ k$-$Heavy Hitter is any element whose frequency is more than

n$/$k$.$ That is$,$ x such that $|\{$i$|$A$[$i$]=$ x$\}|>$ n$/$k$.$

$($a$)$ At most how many k$-$Heavy$-$Hitters are possible?

$($b$)$ Show an algorithm which can find all k$-$heavy hitters in O$($n log k$).$ You may assume n

and k both to be powers of $2.($Hint: Find the median first and then recurse on both

sides. Stop when problem size become $<=$ n$/$k$).$