This is a popular introductory problem that requires implementation of a 'binary search'. Fundamentally, a program keeps track of the lowest and highest possibel values of the solution (initially 1..N). The program then calculates the midpoint and asks whether the midpoint is too high, too low, or just right. The limits are adjusted according to the answer.
While probably among the simplest of algorithms, binary search is one of the most difficult to get right the first time. Why? Because folks just seem to forget that once you know that some midpoint m is, e.g., too high, the new high bound is not m but rather m-1. Failure to change the bounds to m-1 (or m+1) vs. just to m leads to 'corner cases' (conditions that occur near the limits of possible input) that have great potential for error.
Below is the Java solution of USA's Chiranjith Das:
import java.io.*; import java.util.*; public class guess { public static void main (String[] args) throws IOException { BufferedReader in = new BufferedReader (new InputStreamReader (System.in)); int range = Integer.parseInt (in.readLine ()); String response; int low = 1, high = range; do { int guess = (low + high)/2; System.out.println (guess); System.out.flush (); response = in.readLine (); if (response.equals ("H")) high = guess-1; if (response.equals ("L")) low = guess+1; } while (!response.equals ("OK")); System.exit(0); } }