**Good Processor** — Puzzle for Interview rounds

# Question :

You are on a spaceship that has a computer with n processors.

Suddenly, the spaceship gets hit with an alien laser beam, and some of the processors are damaged.

However, you know that more than half of the processors are still good.

You can ask one processor whether it thinks another processor is good or bad. A good processor will always tell the truth, but a bad one will always lie.

A ‘step’ consists of asking one processor if it thinks another processor is good or bad. Find minimum number of steps required to find at least one good processor.

Answer is a integer.

# Solution :

**N-2 is the correct answer.**

Let the processors be numbered 1…n. Begin by asking processor 1 if processor 2 is good. If the answer is “no”, remove these two processors from the list and start over. Note that you removed one good processor and one bad processor from the list, so more than half of the remaining processors are still good.If processor 1 says processor 2 is good, continue by asking processor 2 about processor 3, 3 about 4, etc., until you get a “no” answer. Suppose it is processor j that says processor j+1 is bad. Remove both processors j and j+1 from the list (as before, more than half of the remaining processors are still good, since one of the two you removed was good and one was bad), and continue by asking processor j-1 about processor j (the processor that was after j+1 before you removed it and the original processor j).

You are creating a “chain” of processors who each think the next processor in the chain is good. So these processors are either all good or all bad. Once this chain comprises more than half of the processors in the remaining list, you know that all these processors are good. Or, if you’ve removed so many processors that only one or two remain, you know that that one or those two are good.

To show that this involves at most n-2 steps, note that every processor is asked about at most once, and the first processor is never asked about. Also, the last processor is never asked about either, since you stop once the chain is longer than half the list.