Find majority element — Boyer-Moore voting intuition.

int majority(int[] a) {
  int cand = 0, count = 0;
  for (int x : a) {
    if (count == 0) { cand = x; count = 1; }
    else if (x == cand) count++;
    else count--;
  }
  return cand; // verify if majority guaranteed
}