# 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.

# Solution :

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.

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

--

--

--

## More from Placewit

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

## Placewit

Upskilling students for tech placements!