On Friday 28 September 2007, Sasha Pachev wrote: > A question was asked a friend of mine during his interview with > Microsoft. It is hard to believe that I would have a friend that would > even consider interviewing with Microsoft, or at least I would be > ashamed to admit it on this list, but well, I do :-) > > I decided to port this problem to the New Testament theme, and also > make it more friendly for non-programmers. Anybody who knows how to > use a calculator should be comfortable with it. So here it is: > > You have 100 sheep in a flock and they are all numbered. Each has an > identification tag with a number - 1 through 100. One of them is > lost. Other sheep are scattered over the pasture and cannot be > examined in sequential order of their numbers. Come up with a method > that would allow you to quickly identify the lost sheep. The use of a > simple arithmetical calculator is allowed. The use of a pen or any > other note-taking instrument is not (to disallow the trivial but > unscaleable roll-call method).
Well, depends on how simple the calculator is. As long as it can represent a 100bit number, you can simply examine each sheep and logically or 2^(n-1) to your total until the following is true: log.2(2^(100) - total) is an even integer--which is the number on the missing sheep. (IOW, use a bit field and identify the missing bit) Nick /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
