Above the Average — Solution & Editorial

Back to the Problem

Avoid floating point: a_i > sum/N is the same as a_i·N > sum in exact integer arithmetic.

Complexity: O(N)

Watch out: Comparing against a floating-point mean gives wrong answers on ties; multiply through instead.