Ponder This Challenge - January 2004 - Finding duplicates in read-only array

Ponder This Challenge:

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.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Solution:

  This technique is known as Pollard's rho method; it was developed by John Pollard as a tool for integer factorization.

  Let f(x) be the location of the array at address x.

  a := f(f(n))
  b := f(n)
  do while not (a=b)
  a:=f(f(a))
  b:=f(b)
  end
  /* Now a=b can be reached at either 2k or k steps from n, */
  /* where k is some integer between 1 and n. */
  a:=n
  do while not (a=b)
  a:=f(a)
  b:=f(b)
  end
  print a

  The pattern that you get, starting from n and repeatedly applying f (doing the table lookup), is a string of some length L>0 leading to a cycle of some length M, with L+M<n. (L is nonzero because n is outside the range of f.)
  It is shaped like the Greek letter rho, hence its name. Our stopping count k is the least multiple of M greater than or equal to L, so that L \leq k < L+M < n.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Hagen von Eitzen (1.5.2004 @12:45:38 PM EDT)
• Brand Michael (1.5.2004 @2:33:43 PM EDT)
• Patrick J. LoPresti (1.5.2004 @6:29:22 PM EDT)
• Juergen Stuber (1.5.2004 @6:29:22 PM EDT)
• Ilan Algor (1.6.2004 @4:13:38 AM EDT)
• Bill Roscoe (1.6.2004 @4:43:19 AM EDT)
• Peter Kormushev & Angel Velikov (1.6.2004 @7:47:51 AM EDT)
• Michael Swart (1.6.2004 @10:56:39 AM EDT)
• Nilesh Dalvi (1.6.2004 @11:44:54 AM EDT)
• David McQuillan (1.6.2004 @6:17:08 PM EDT)
• Bart De Vylder (1.7.2004 @8:49:04 PM EDT)
• Graeme McRae (1.8.2004 @12:06:38 PM EDT)
• Dharmadeep Muppalla (1.9.2004 @12:25:49 AM EDT)
• rodentofdarkness (1.9.2004 @12:06:57 PM EDT)
• Andre Rzym (1.9.2004 @6:47:41 PM EDT)
• Simon Frankau (1.9.2004 @7:16:32 PM EDT)
• IQSTAR (1.10.2004 @3:47:05 AM EDT)
• Coserea Gheorghe (1.10.2004 @5:54:37 AM EDT)
• Narayanan Rajamani (1.10.2004 @7:44:06 AM EDT)
• Johannes Schindelin (1.11.2004 @11:19:37 AM EDT)
• Bertram Felgenhauer (1.11.2004 @9:47:31 PM EDT)
• Ed Sheppard (1.12.2004 @5:32:27 PM EDT)
• Jeff Zhang (1.12.2004 @5:42:56 PM EDT)
• Gabi Zuniga (1.13.2004 @1:58:18 AM EDT)
• Michael Harris (1.13.2004 @7:11:36 PM EDT)
• Piotr Zielinski (1.13.2004 @10:00:03 PM EDT)
• Yao Ziyuan (1.14.2004 @5:41:24 AM EDT)
• Dan Milstein (1.14.2004 @12:18:25 PM EDT)
• Renaud Bauvin (1.14.2004 @1:17:36 PM EDT)
• bartosz Nowierski (1.15.2004 @2:06:17 AM EDT)
• Daniel Bitin (1.16.2004 @4:51:28 AM EDT)
• Jerome Neyrat (1.16.2004 @2:30:27 PM EDT)
• Christopher Hendrie (1.16.2004 @2:52:54 PM EDT)
• Alexander Grushetsky (1.17.2004 @9:29:09 AM EDT)
• Eugene Vasilchenko (1.17.2004 @12:33:04 PM EDT)
• Michael Schatz (1.17.2004 @3:48:31 PM EDT)
• Tomas Rokicki (1.17.2004 @4:15:38 PM EDT)
• David Woodruff (1.18.2004 @12:15:43 AM EDT)
• Jakub Łopuszański (1.18.2004 @2:23:46 PM EDT)
• Walter Guttman (1.19.2004 @10:03:29 AM EDT)
• Matt Paterson (1.19.2004 @10:04:43 PM EDT)
• Eric Thierry (1.19.2004 @3:13:51 PM EDT)
• Markus Kuhn (1.20.2004 @9:07:39 AM EDT)
• David Friedman (1.20.2004 @11:50:21 AM EDT)
• Negruseri Cosmin (1.20.2004 @2:40:58 PM EDT)
• Bogusław Kluge (1.20.2004 @4:41:22 PM EDT)
• Jayavel Sounderpandian (1.21.2004 @11:09:22 AM EDT)
• Joe Fendel (1.21.2004 @4:42:22 PM EDT)
• Roland Dreier (1.21.2004 @10:28:18 PM EDT)
• Clive Tong (1.22.2004 @6:11:28 AM EDT)
• Lars Hellsten (1.22.2004 @2:27:26 PM EDT)
• Christopher Howe (1.22.2004 @5:29:42 PM EDT)
• trusso (1.22.2004 @6:26:20 PM EDT)
• Patrick Hohmeyer (1.23.2004 @1:44:48 AM EDT)
• Kenneth Halpern (1.23.2004 @2:59:57 PM EDT)
• Anatoly Morosov (1.23.2004 @4:56:48 PM EDT)
• Pascal Brisset (1.23.2004 @10:22:12 PM EDT)
• Brad Austin (1.24.2004 @6:52:19 AM EDT)
• Pawel Lichocki (1.24.2004 @7:03:56 AM EDT)
• Chuck "Rustyoldman" Grant (1.24.2004 @8:30:10 AM EDT)
• Guler Amos (1.25.2004 @3:26:59 PM EDT)
• Steve Powell (1.26.2004 @3:59:53 AM EDT)
• John Pollard (1.26.2004 @8:48:00 AM EDT)
• Steven Schveighoffer (1.26.2004 @3:27:40 PM EDT)
• Mathijs Vogelzang (1.26.2004 @4:54:07 PM EDT)
• John V Sichi (1.27.2004 @3:15:10 AM EDT)
• Steven Murdoch (1.27.2004 @1:11:11 PM EDT)
• Frederico Prat Villar (1.27.2004 @2:56:40 PM EDT)
• Daniel Chong Jyh Tar (1.28.2004 @10:55:06 AM EDT)
• Harvard Pettersen (1.28.2004 @11:01:42 AM EDT)
• Arne H Juul (1.28.2004 @11:11:37 AM EDT)
• Øyvind Grotmo (1.28.2004 @3:53:45 PM EDT)
• l (1.28.2004 @3:53:45 PM EDT)
• Erling Ellingsen (1.29.2004 @5:00:34 PM EDT)
• Ivelin Ivanov (1.30.2004 @1:02:21 AM EDT)
• Emile Joubert (1.30.2004 @8:42:37 AM EDT)
• Dennis Langdeau (1.30.2004 @4:56:18 PM EDT)
• Jeff Shute (1.31.2004 @2:52:44 AM EDT)
• Yale Theory Clique (1.31.2004 @4:17:18 AM EDT)
• Aleksey Pinkin (1.31.2004 @11:14:37 AM EDT)
• Troels Nørgaard (2.01.2004 @4:49:57 AM EDT)
• Wojciech Jaśkowski (2.01.2004 @1:35:21 PM EDT)
• Nagi Nahas (2.01.2004 @3:31:26 PM EDT)