Exact (n + 1) Comparison Complexity for the N-Repeated Element Problem

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.