Abstract:This paper establishes the exact comparison complexity of finding an element repeated $n$ times in a $2n$-element array containing $n+1$ distinct values, under the equality-comparison model with $O(1)$ extra space.
We present a simple deterministic algorithm performing exactly $n+1$ comparisons and prove this bound \emph{tight}: any correct algorithm requires at least $n+1$ comparisons in the worst case.
The lower bound follows from an adversary argument using graph-theoretic structure. Equality queries build an \emph{inequality graph} $I$; its complement $P$ (potential-equalities) must contain either two disjoint $n$-cliques or one $(n+1)$-clique to maintain ambiguity. We show these structures persist through $n$ comparisons via a ``pillar matching'' construction, but cannot survive the $(n+1)$st. The matching upper bound comes from a ``triangle'' construction that forces every component of $I$ to be a clique, so each hosts at most one copy of the repeated element and the single untested element must be the answer.
This result provides a concrete, self-contained demonstration of exact lower-bound techniques, bridging toy problems with nontrivial combinatorial reasoning.
From: Andrew Au [view email]
[v1]
Wed, 28 Jan 2026 00:09:31 UTC (7 KB)
[v2]
Fri, 6 Feb 2026 03:50:02 UTC (7 KB)
[v3]
Wed, 9 Sep 2026 02:19:11 UTC (8 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。