Simple deterministic O(n log n) algorithm finding a solution of Erdős-Ginzburg-Ziv theorem
share
Erdős-Ginzburg-Ziv theorem is a famous theorem in additive number theory, which states any sequence of 2n-1 integers contains a subsequence of n elements, with their sum being a multiple of n. In this article, we provide an algorithm finding a solution of Erdős-Ginzburg-Ziv theorem in 𝒪(n log n) time. This is the first known deterministic 𝒪(n log n) time algorithm finding a solution of Erdős-Ginzburg-Ziv theorem.
READ FULL TEXT