IBM Ponder This #069 · January 2004

This month's puzzle was sent in by Joe Buhler.
It came from a SIGCSE meeting via Eric Roberts.

A read-only array of length n, with address from 1 to n inclusive,
contains entries from the set {1, 2, ..., n-1}.
By Dirichlet's Pigeon-Hole Principle there are one or more duplicated
entries. Find a linear-time algorithm that prints a duplicated value,
using only "constant extra space". (This space restriction is important;
we have only a fixed number of usable read/write
memory locations, each capable of storing an integer between 1 and n.
The number of such locations is constant, independent of n.
The original array entries can not be altered.) The algorithm should
be easily implementable in any standard programming language.

Solution

Best opened after a real attempt

To be added.