An array of n integers contains one value that appears more than n/2 times (a strict majority). Find it.
Constraints: one pass over the array, O(1) extra memory. No hash map, no sorting.
Example: [2, 7, 2, 2, 5, 2, 2, 7] gives 2 (5 of 8).
A hint without spoilers: pairs of different elements can cancel each other out.
Follow-up for later: what if there is no guarantee that a majority exists?