Abstract / Summary

Given four soup servings, count how many ways to serve them to two people until one has no soup left.

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 60% (200k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Math
• Probability And Statistics

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 computes a probability value based on two integer parameters that are progressively reduced through a recursive process. The public entry point is soupServings, which first checks for a threshold condition, then scales the input to a smaller domain before delegating the core computation to the helper method deeper. The helper method uses memoization to avoid redundant work and evaluates four possible transitions at each recursive step, ultimately returning a floating-point result.

Key Steps

Early termination for large inputs

if n > 4900:
    return 1

When the original argument exceeds a predefined bound, the function immediately returns the maximal probability value. This shortcut prevents the algorithm from exploring an excessively deep recursion tree for inputs that are known to converge to the limiting result.

Scaling the state space

simpler = (n + 24) // 25
return self.deeper(simpler, simpler)

The input n is transformed by rounding up to the nearest multiple of 25 and then dividing by 25. This reduction maps the original problem onto a much smaller integer lattice while preserving the relative proportions required for the recursive evaluation. The scaled value is used as both arguments to deeper, establishing a symmetric starting state.

Recursive probability calculation with memoization

@cache
def deeper(self, a, b):
    emptyA = a <= 0
    emptyB = b <= 0
    if emptyA and emptyB:
        return 0.5
    if emptyA:
        return 1
    if emptyB:
        return 0

    m = self.deeper(a - 4, b)
    n = self.deeper(a - 3, b - 1)
    o = self.deeper(a - 2, b - 2)
    p = self.deeper(a - 1, b - 3)
    return (m + n + o + p) / 4

The deeper method is decorated with @cache, which automatically stores the result of each unique (a, b) pair. This memoization ensures that each sub-problem is solved at most once, turning an exponential recursion into a tractable dynamic programming solution.

The method first determines whether either argument has reached a non-positive value. If both are non-positive, the function returns a neutral probability of 0.5. If only the first argument is non-positive, the result is 1, indicating a favorable outcome for that side; conversely, if only the second argument is non-positive, the result is 0.

When neither argument is exhausted, the function explores four possible reductions of the state: decreasing a by 4 while leaving b unchanged, decreasing a by 3 and b by 1, decreasing both by 2, and decreasing a by 1 while decreasing b by 3. The results of these four recursive calls are averaged, reflecting an equal probability of each transition occurring.

Edge Cases Handled

The base conditions explicitly address the scenario where both parameters have become non-positive simultaneously, returning a midpoint probability. The case where only the first parameter is non-positive yields the maximal probability, while the symmetric case for the second parameter yields the minimal probability. These conditions guarantee that the recursion terminates correctly even when the decrement steps overshoot the zero boundary.

The scaling step uses integer division with rounding up, ensuring that any positive n maps to at least one unit in the reduced domain. This prevents a degenerate situation where the scaled value could become zero before the recursion begins, which would otherwise trigger the base case prematurely.

The early return for n > 4900 handles extremely large inputs by recognizing that the probability converges to the upper bound, thereby avoiding unnecessary recursion depth and potential stack overflow.

Performance Optimizations

Memoization via the @cache decorator eliminates repeated evaluation of identical sub-problems, turning the naive exponential recursion into a polynomial-time computation over the reduced state space. The scaling of the input by a factor of 25 dramatically shrinks the number of distinct (a, b) pairs that need to be explored, reducing both the number of recursive calls and the size of the cache.

The explicit cutoff for inputs larger than 4900 provides a constant-time shortcut for a substantial portion of the input domain, bypassing the recursive machinery entirely. By rounding up during the scaling step, the implementation ensures that the reduced problem size is as small as possible while still preserving correctness, further limiting the depth of the recursion tree.

Collectively, these techniques produce a solution that runs efficiently even for inputs near the upper bound of the problem’s constraints, delivering the final probability with minimal computational overhead.

Imagine there are two large bowls of delicious soup. Some bowls are almost empty and others are very full. The computer is trying to figure out what happens if you keep serving spoonfuls of soup until the bowls run out.

The first part of the code checks if there is any soup left. If both bowls become empty at the exact same time, it counts that as a tie. If the first bowl runs out before the second one, it declares a win for the first bowl. If the second bowl runs out first, it marks that as a loss for the first bowl.

When there is plenty of soup, the code pretends to be a little robot that keeps scooping out soup in four different ways. It takes a different amount from each bowl until there is nothing left to scoop. Because there are four different ways to scoop, it adds up the results and divides them by four to find the average.

Sometimes the bowls are so big that the first bowl will almost certainly run out first, no matter what happens. The code is smart enough to know that if the bowls are bigger than a certain size, it can stop guessing and just say the first bowl wins. It also makes the math easier by shrinking the big bowls down into smaller portions so the computer does not get tired while counting. It remembers the answers it already found so it does not have to do the same work again.

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++	Rust		Java	C#	Go	Python	TS
	LeetcodeHelp	C++			Java			Python
	Progiez	C++			Java			Python
github	black-shadows	C++
	charles-wangkai				Java
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	ruoru		Rust
	suxrobGM					C#
	wisdompeak	C++
	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
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
ruoru	Rust
suxrobGM	C#
wisdompeak	C++
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