Abstract / Summary

Guess a number between one and n using higher or lower hints until finding the correct number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (1+ million submissions).

Typical patterns to solve this problem:

• Binary Search
• Interactive

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The presented Solution class implements a number-guessing routine that interacts with an external guess API. The algorithm searches for a hidden integer within the range [1, 2^31-1] by repeatedly adjusting a candidate value (pick) based on the feedback (hint) returned by guess. The core idea is a binary-search-like narrowing of the search interval, realized through bit-wise operations that avoid costly arithmetic.

Key Steps

The method guessNumber follows a deterministic sequence of actions:

1. Initial candidate and step size

   int64_t pick = 1 << 30; // halfway between 1 and 2^31 - 1
   int64_t step = pick >> 1;

   The initial pick is set to 2^30, which is the midpoint of the full search space. The accompanying step is half of that value, establishing the first adjustment magnitude.

2. Iterative probing loop

   while (true)
   {
       auto hint = guess(pick);
       if (hint == 0)
           break;
   
       pick += step * hint;
       step >>= 1;
   }

   Inside the infinite loop, the code queries the guess function with the current pick. The returned hint can be 0 (correct), -1 (target is lower), or 1 (target is higher). A zero hint terminates the loop. Otherwise, pick is moved toward the target by adding step multiplied by the sign of hint. After each adjustment, step is halved using a right shift, progressively refining the search granularity.

3. Result return

   return pick;

   When the loop exits, pick holds the exact hidden number, which is then returned to the caller.

Edge Cases Handled

The algorithm gracefully accommodates the extreme bounds of the search interval. By initializing pick to 2^30 and step to 2^29, the first adjustment can reach both the lower bound (1) and the upper bound (2^31-1) in a single step if the hidden number lies at either extreme. The use of a signed hint multiplier (-1 or 1) ensures that the direction of movement is correctly applied regardless of whether the target is above or below the current pick. The loop continues until step becomes zero, at which point the only remaining possible value is the correct one, guaranteeing termination even when the hidden number is adjacent to the initial midpoint.

Performance Optimizations

The implementation leverages several low-level techniques to maximize efficiency:

• Bit-wise initialization: Setting pick with 1 << 30 and deriving step via pick >> 1 avoids multiplication or division, yielding faster compile-time constants.
• Shift-based step reduction: Halving step with step >>= 1 is a constant-time operation that replaces arithmetic division, reducing CPU cycles per iteration.
• Multiplication by hint: The expression step * hint uses the sign of hint to either add or subtract step without branching, allowing the compiler to generate streamlined arithmetic instructions.
• 64-bit arithmetic: Declaring pick and step as int64_t prevents overflow when intermediate values exceed the 32-bit range, eliminating the need for additional checks and keeping the loop tight.
• Early exit: The loop terminates immediately upon receiving a zero hint, avoiding unnecessary iterations once the target is found.

Collectively, these choices produce a compact, high-throughput search routine that converges on the hidden number in a logarithmic number of steps while maintaining minimal overhead per iteration.

Imagine a giant game of find the hidden number where a computer has picked a mystery digit and you need to guess what it is. The game is helpful because it tells you if your guess is too high, too low, or exactly right. This code acts like a very smart player that plays the game using a special strategy.

It starts by picking a number right in the middle of all the possible choices. After it makes a guess, the game gives a little hint. If the hint tells the code that the guess was too high, it knows it needs to choose a smaller number next. If the hint says the guess was too low, it tries a bigger number.

The code uses a clever trick where it makes the jumps smaller each time. It starts by taking a huge leap to narrow down the playing field, and with every step, it cuts the size of that leap in half. By doing this over and over, it zooms in on the secret number very quickly. It keeps repeating this motion until the hint says zero, which is the signal that the secret number has been found.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java		Python							TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java	C#	Python				Go		Rust	TS
	LeetcodeHelp	C++	Java		Python
	Progiez	C++	Java		Python
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai		Java
	chenyanzhe	C++
	Dijkstra-Edu		Java
	DimitrisJim									C
	fartem					Ruby
	halfrost								Go
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	linouk23	C++
	lkwq007				Python
	qiyuangong				Python
	shreymehul			C#
	suxrobGM			C#
	varunu28		Java
	vthwang		Java
	XiaotaoGuo	C++
	yuanliu666						Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	C
fartem	Ruby
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
linouk23	C++
lkwq007	Python
qiyuangong	Python
shreymehul	C#
suxrobGM	C#
varunu28	Java
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality