Skip to content

Instantly share code, notes, and snippets.

@aashutoshrathi
Last active December 9, 2018 08:23
Show Gist options
  • Save aashutoshrathi/0412606094bfe28b77f6b1506eedd6f6 to your computer and use it in GitHub Desktop.
Save aashutoshrathi/0412606094bfe28b77f6b1506eedd6f6 to your computer and use it in GitHub Desktop.

Problem - 3 (Medium)

Bharat: "Hey, Amar!"

Amar: "Yes, I know. You want to play 'Guess a Number.' I'll play the two-round version where you submit a list of yes/no questions, then I answer them, and then you guess one number."

Bharat: "Okay! So..."

Amar: "But I will not answer all of your questions. I will leave one question (of my choosing) unanswered."

Bharat: "Oh..."

Amar: "Still want to play?"

Bharat: "Yes!"

So, Amar thinks of a number between 1 and 1000, and Bharat makes up a list of questions.

Amar then receives the list, selects one question to leave blank, answers all of the other questions with yes or no, and returns the list to Bharat.

Now Bharat must guess Amar's number and, if he is wrong, he loses.

How many questions does Bharat need to ask (non-adaptively) in order to correctly identify Amar's number and guarantee a win?

PS: Bharat knows that Amar will be chosing a number between 1 to 1000.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment