if i were asked a secret question between 1 and 1 billion by asking yes/no question of the form "is the number less than X?
" what algo should i use to efficiently find the secret number?
using the algo what will be the minimum number of questions if asked will guarantee to find
the secret number???
Builder_1 -6 Junior Poster in Training
Moschops 683 Practically a Master Poster Featured Poster
You can make it easier to think about by pretending the number is between one and ten. The algorithm is identical.
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
Just think of the number in in its binary representation.
What question will tell you the value of the first bit?
Knowing that, what question will tell you the value of the next bit?
How many questions will you need to know the values of all the bits?
umairs007 0 Newbie Poster
It will be Binary Search
And Also 1000000 = 2^30
So Questions will be Log(2^30) = 30
Builder_1 -6 Junior Poster in Training
cant it be done with recursion... and 2^30 is 1000000000 not 1000000
Builder_1 -6 Junior Poster in Training
kindly someone to guide that instead of binary search..cant it be done with recursion???
SalmiSoft 102 Junior Poster
A binary search may be implemented using recursion. Take a look at
http://rosettacode.org/wiki/Binary_search#C.2B.2B
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.