TopCoder Statistics - Problem Statement

Problem Statement

A popular guessing game is "Guess the number", where one person selects a number in a known range, and another person tries to guess that number. After each guess, the first person reveals whether the guess was correct, too high or too low.

Pretty soon one learns the best strategy, which is to guess the middle number among those not yet ruled out. If there is no single middle number, then there are two numbers to choose from. In that case, we choose the smallest of those numbers.

The algorithm can be described like this:

Init lower and upper bound
Repeat
  x = (lower bound + upper bound)/2  (round down if necessary)
  Make guess x
  If x is too low, set lower bound to x+1
  If x is too high, set upper bound to x-1
Until x is correct

For instance, assume that the lower and upper bound initally are 1 and 9, respectively. The middle number in this range is 5. If this is "too low", the new bounds become 6 and 9. This range contains four numbers, and there is thus no single middle number. The two numbers in the middle are 7 and 8, and the smallest of these is 7, so our next guess then becomes 7.

Create a class GuessTheNumber which contains the method noGuesses which takes an int upper, the initial upper bound of the range (the inital lower bound is always 1), and an int answer, the number selected by the first person. The method should return an int representing the total number of guesses required for the second person to guess the correct number using the method described above.

Definition

Class:: GuessTheNumber
Method:: noGuesses
Parameters:: int, int
Returns:: int
Method signature:: int noGuesses(int upper, int answer)
(be sure your method is public)

Constraints

upper will be between 1 and 1000, inclusive.
answer will be between 1 and upper, inclusive.

Examples

9

6

Returns: 3

The first guess will be (1+9)/2=5, which is too low. The new lower bound then becomes 5+1=6. The second guess then becomes (6+9)/2=7, which is too high. The new upper bound then becomes 7-1=6. The third guess is then of course (6+6)/2)=6, which is correct. So, three guesses were required, and the method thus returns 3.
1000

750

Returns: 2

The first guess will be 500, the second guess 750.
643

327

Returns: 7

The guesses are 322, 483, 402, 362, 342, 332 and finally 327, so the method returns 7.
157

157

Returns: 8

Here the guesses are 79, 118, 138, 148, 153, 155, 156 and finally 157. The method thus returns 8.
263

215

Returns: 8
701

258

Returns: 9
753

643

Returns: 10
257

234

Returns: 8
712

680

Returns: 9
844

390

Returns: 10
109

61

Returns: 4
331

190

Returns: 9
170

43

Returns: 7
918

720

Returns: 8
973

836

Returns: 6
981

908

Returns: 8
550

293

Returns: 9
165

50

Returns: 8
552

468

Returns: 9
191

106

Returns: 7
636

561

Returns: 10
945

81

Returns: 10
863

249

Returns: 7
364

66

Returns: 8
711

55

Returns: 6
877

265

Returns: 9
930

518

Returns: 10
676

588

Returns: 10
191

108

Returns: 4
135

86

Returns: 7
630

481

Returns: 10
728

431

Returns: 10
744

191

Returns: 7
105

71

Returns: 7
750

621

Returns: 6
257

13

Returns: 8
573

33

Returns: 9
491

347

Returns: 8
120

46

Returns: 6
696

162

Returns: 10
328

144

Returns: 8
498

411

Returns: 9
597

250

Returns: 10
357

102

Returns: 7
94

46

Returns: 7
8

3

Returns: 3
510

45

Returns: 8
353

113

Returns: 8
784

179

Returns: 10
802

219

Returns: 9
331

180

Returns: 9
196

117

Returns: 7
964

136

Returns: 9
428

323

Returns: 9
107

48

Returns: 6
213

61

Returns: 8
511

344

Returns: 6
659

395

Returns: 10
332

327

Returns: 6
848

677

Returns: 10
198

10

Returns: 7
439

79

Returns: 9
19

2

Returns: 3
128

64

Returns: 1
1

1

Returns: 1
2

1

Returns: 1
2

2

Returns: 2
2

2

Returns: 2
1

1

Returns: 1
157

157

Returns: 8
3

3

Returns: 2

Statistics

Problem Statement for "GuessTheNumber"

Problem Statement

Definition

Constraints

Examples