public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int winner = array[0];
        int troops = 1;
        // loop terminate condition:
        // i < array.length && troop < array.length - i (if troops > rest of array, game ends)
        for (int i = 1; i < array.length - troops; i++) {
            if (troops == 0) {
                winner = array[i];
                troops = 1;
            } else {
                troops += array[i] == winner ? 1 : -1;
            }
        }
        return winner;
    }
}