The Lost Sheep Challenge

Nicholas Leippe nick at leippe.com
Fri Sep 28 16:15:17 MDT 2007


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




More information about the PLUG mailing list