Notice that we can always construct an optimal solution with simple greedy approach, i.e., if a(i) < a(j), we know there exists an optimal solution where numberOfLeader(i) >= numberOfLeader(j). Reason: we can force a(i) to be leader until a(j) is reduced to a(i), and then each of them takes turns to be leader.

Also notice we are looking for the minimum number, i.e., the answer is monotonic, i.e., if m satisfies conditions, so does m + 1

Suppose we know final answer m, given the greedy insight, we can find the solution as follows,

  1. a(1) is leader for m - a(1) games

  2. a(2) is the leader for (m - a(1)) - (a(2) - a(1)) games = m -a(2)

  3. a(3) is the leader for (m - (a(1) + a(2))) - (a(3) - (a(1) + a(2))) games = m - a(3)...and so on

Since m also is number of games a(i) being leaders, we know m <= m - a(1) + m - a(2) + m - a(3)….. Solve it and we get lower bound for m