{"id":"arxiv/2605.21753","url":"https://arxiv.org/abs/2605.21753","tags":["cs.DS","math.CO"],"score":0,"title":"Finding a Solution to the Erdős-Ginzburg-Ziv Theorem in Linear Time","domain":"cs.DS","source":"arxiv","authors":["Sunghyeon Jo"],"reviews":0,"subject":"cs.DS","summary":"The Erdős-Ginzburg-Ziv theorem states that every sequence of 2n - 1 integers contains a subsequence of length n whose sum is divisible by n. Choi, Kang, and Lim gave a simple deterministic O(n log n) algorithm for finding such a subsequence, and Leung recently improved this to O(n log log log n). We give a deterministic linear-time algorithm. The core is a linear-time algorithm for the following prime target subset-sum problem: given p - 1 nonzero residues in Z_p and a target residue, find a subset with the prescribed sum. Our algorithm maintains a compact arithmetic-progression…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-20","reactions":{}}