January 2004
<<December January February>>
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
Challenge:
01/03/04 @ 01:00 PM ET
Solution:
02/02/04 @ 05:00 PM ET
List Updated:
02/13/04 @ 4:00 PM ET
People who answered correctly:
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 Grotmol (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)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.