Find the majority element, which appears more than half the time
If it is known that a majority element exists, then the efficient algorithm to use is the Boyer-Moore majority vote algorithm, which requires only O(1) space.