Abstract / Summary

Find the minimum amount of money needed to guarantee a win when guessing a hidden number from one to n using higher or lower hints.

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 53% (300k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Game Theory
• Math

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 provided implementation solves the classic “Guess Number Higher or Lower II” problem using a top-down dynamic programming approach with memoization. The Solution class exposes a single public method getMoneyAmount that computes the minimum amount of money required to guarantee a win for any secret number in the range 1 to n. The core of the algorithm is a recursive helper deeper that evaluates the optimal cost for any sub-interval [left, right]. By caching intermediate results, the solution avoids redundant recomputation and achieves efficient performance for moderate values of n.

Core Recursive Logic

The heart of the algorithm lies in the deeper function, which returns the minimal worst-case cost for guessing a number within a given interval.

@cache
def deeper(left, right):
    if left >= right:
        return 0

    best = 9999999999
    choice = -1
    for mid in range(left, right + 1):
        l = deeper(left, mid - 1)
        r = deeper(mid + 1, right)
        current = mid + max(l, r)
        if best > current:
            best = current
            choice = mid
    return best

The function first checks the base condition if left >= right. When the interval collapses to a single number or becomes empty, no cost is incurred because the correct number is already known; the function returns 0.

The loop iterates over every possible pivot mid within the current interval. For each pivot, the algorithm recursively computes the cost of the left sub-interval (l) and the right sub-interval (r). The worst-case cost for choosing mid is the price of the guess itself (mid) plus the larger of the two sub-interval costs, expressed as mid + max(l, r). The algorithm tracks the smallest such worst-case cost in best and records the corresponding pivot in choice. Finally, best is returned as the optimal cost for the interval.

Entry Point

The public method simply initiates the recursion for the full range from 1 to n.

def getMoneyAmount(self, n: int) -> int:
    return deeper(1, n)

By delegating to deeper, the method leverages the memoized recursion to compute the answer efficiently.

Edge-Case Handling

The base case if left >= right: return 0 gracefully handles two edge situations:

• When left == right, the interval contains exactly one possible number. No guess is needed because the number is already determined, so the cost is zero.
• When left > right, the interval is empty, which can occur when a recursive call evaluates a sub-interval that lies completely outside the original bounds (e.g., after selecting the smallest or largest possible pivot). Returning zero in this scenario correctly reflects that no further expenditure is required.

These conditions ensure that the recursion terminates correctly for all possible sub-interval configurations.

Performance Optimizations

The most significant optimization is the use of the @cache decorator from Python’s functools. This decorator automatically memoizes the results of deeper for each unique pair (left, right). Consequently, each distinct sub-interval is evaluated at most once, turning an exponential recursion into a polynomial-time computation. The cache eliminates the need for explicit table construction while preserving the clarity of the recursive formulation.

Another subtle optimization is the early termination of the inner loop when a better best value is found. Although the code still examines every possible mid, the comparison if best > current: ensures that only improvements update the tracking variables, avoiding unnecessary assignments.

The choice of a very large sentinel value (9999999999) for best guarantees that any legitimate cost will replace it on the first iteration, simplifying the initialization logic without additional condition checks.

Summary of Execution Flow

When getMoneyAmount is called, the algorithm starts with the full interval [1, n]. The recursive helper explores all possible first guesses, recursively solving the left and right sub-problems for each guess. Thanks to memoization, each sub-interval’s optimal cost is stored after its first computation, so subsequent references retrieve the cached value instantly. The recursion unwinds, propagating the minimal worst-case costs upward until the initial call returns the final answer. This approach systematically evaluates the decision tree of guesses while keeping the number of distinct sub-problems bounded by the number of interval pairs.

Imagine there is a game where someone picks a mystery number between one and a big number like ten. You have to guess the right number, but every time you guess wrong, you have to pay a little bit of money equal to the number you guessed. To win, you want to be very smart and spend the least amount of money possible, no matter which number the other person picked.

The computer does this by trying out every single number as a potential first guess. It looks at the left side of the number range and the right side of the number range separately to see how much money that guess would cost in the worst case scenario. By checking every single possibility, it finds the exact spot where the cost is as low as it can be. Once it finds that, it remembers the answer for that specific range so it does not have to do all that hard counting again. It keeps splitting the numbers up and testing them over and over until it knows the best way to play the game from start to finish.

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

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java				Go	TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	chenyanzhe	C++
	everthis			JS
	JoshCrozier			JS
	linouk23	C++
	lkwq007		Python
	lzl124631x	C++
	qiyuangong		Python
	ruoru						Rust
	suxrobGM					C#
	varunu28				Java
	vli02							C
	wisdompeak	C++
	XiaotaoGuo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
lzl124631x	C++
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	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