2022/08/16 by Choi, Seokhwan, Kang, Hanpil, Lim, Dongjae · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2208.07728
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 O(n log n) time. This is the first known deterministic O(n log n) time algorithm finding a solution of Erdős-Ginzburg-Ziv theorem.