Simple deterministic O(n log n) algorithm finding a solution of Erd\H{o}s-Ginzburg-Ziv theorem

arXiv2208.07728MaRDI QIDQ6408003FDOQ6408003

Authors: Seokhwan Choi, Hanpil Kang, Dongjae Lim 

Publication date: 16 August 2022

Abstract: ErdH{o}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 ErdH{o}s-Ginzburg-Ziv theorem in $mathcalO(nlogn)$ time. This is the first known deterministic $mathcalO(nlogn)$ time algorithm finding a solution of ErdH{o}s-Ginzburg-Ziv theorem.

Has companion code repository: https://github.com/ho94949/egz

This page was built for publication: Simple deterministic O(n log n) algorithm finding a solution of Erd\H{o}s-Ginzburg-Ziv theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408003)