An array $A[1$dotsn$]$ is said to have a majority element if more same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so$,$ to find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form $"$is $A[i]>A[j]?".($Think of the array elements as GIF files, say.$)$ However you can answer questions of the form: $"$is $A[i]=A[j]?"$ in constant time.