Placements around the Corner

With the placement fever raging, thought I would contribute something to keep the fire burning. So decided to put up some interesting problems that I come across on this blog. Will try to keep the posts as regular as possible. But of course I get to define what regular actually means!!

To start off, here’s a classical programming problem:

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.

Hint: The solution is similar to the problem of finding loops in a linked list in one traversal. Hints are auto generated by Agent Pal and may or may not actually be of any real use.

Please use the comments section to discuss the solution.