LeetCode 808: Soup Servings
A probability dynamic programming solution for computing whether soup A empties before soup B, with an early return for large input.
Problem Restatement
We have two soups, A and B. Both start with n milliliters.
On each turn, one of four operations is chosen with equal probability 0.25:
| Operation | Soup A served | Soup B served |
|---|---|---|
| 1 | 100 ml | 0 ml |
| 2 | 75 ml | 25 ml |
| 3 | 50 ml | 50 ml |
| 4 | 25 ml | 75 ml |
If an operation asks for more soup than remains, we serve all that remains.
The process stops immediately after a turn where at least one soup becomes empty.
Return:
P(A empties first) + 0.5 * P(A and B empty at the same time)
Answers within 10^-5 of the actual answer are accepted.
Input and Output
| Item | Meaning |
|---|---|
| Input | An integer n, the starting amount of each soup |
| Output | A probability as a floating-point number |
| Stop condition | Stop after a turn where A or B becomes empty |
| Tie rule | If both empty together, count half of that probability |
| Accepted error | 10^-5 |
Examples
Example 1:
n = 50
Each soup starts with 50 ml.
The four possible first operations give:
| Operation | Result |
|---|---|
Serve 100, 0 |
A becomes empty first |
Serve 75, 25 |
A becomes empty first |
Serve 50, 50 |
A and B become empty together |
Serve 25, 75 |
B becomes empty first |
So the probability is:
0.25 * (1 + 1 + 0.5 + 0) = 0.625
The answer is:
0.625
Example 2:
n = 100
The answer is:
0.71875
First Thought: Brute Force
A direct recursive solution can simulate all possible serving sequences.
From each state (a, b), where a and b are the remaining soup amounts, we try all four operations.
The probability from that state is the average of the probabilities from the four next states.
This gives the right recurrence, but without memoization it repeats the same states many times.
Key Insight
All serving amounts are multiples of 25.
So instead of working in milliliters, we can work in units of 25 ml.
The operations become:
| Operation | Soup A units | Soup B units |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 1 |
| 3 | 2 | 2 |
| 4 | 1 | 3 |
If n is not a multiple of 25, we round up:
units = (n + 24) // 25
This is safe because serving more than the remaining amount simply empties the soup.
Now define:
dp(a, b)
as the probability that we want, starting with a units of soup A and b units of soup B.
Algorithm
Use memoized recursion.
Base cases:
| Condition | Return value | Reason |
|---|---|---|
a <= 0 and b <= 0 |
0.5 |
Both soups empty together |
a <= 0 |
1.0 |
A empties first |
b <= 0 |
0.0 |
B empties first |
Recursive case:
dp(a, b) = 0.25 * (
dp(a - 4, b) +
dp(a - 3, b - 1) +
dp(a - 2, b - 2) +
dp(a - 1, b - 3)
)
There is also an important optimization.
For large n, the probability approaches 1.0, because soup A is served more on average than soup B. LeetCode accepts answers within 10^-5, so we can return 1.0 once n is large enough. A common accepted cutoff is n >= 4800.
Correctness
The function dp(a, b) represents the exact probability required by the problem from a state with a units of soup A and b units of soup B remaining.
If both values are non-positive, both soups became empty on the same turn, so the contribution is 0.5.
If only a is non-positive, soup A became empty first, so the contribution is 1.0.
If only b is non-positive, soup B became empty first, so the contribution is 0.0.
For any state where both soups remain, the next operation is chosen uniformly from the four serving operations. Therefore, the probability from the current state is the average of the probabilities from the four possible next states.
The recursion exactly follows this transition rule, and memoization only reuses already computed state values without changing them. Therefore, dp(units, units) returns the required probability.
The early return for large n is valid for the accepted-error setting because the probability converges to 1.0, and the cutoff is chosen so the error is within the required tolerance.
Complexity
Let:
u = ceil(n / 25)
| Metric | Value | Why |
|---|---|---|
| Time | O(u^2) |
There are at most u * u states |
| Space | O(u^2) |
Memoization stores state results |
With the large-n cutoff, the number of computed states is bounded by a constant in accepted submissions.
Implementation
from functools import cache
class Solution:
def soupServings(self, n: int) -> float:
if n >= 4800:
return 1.0
units = (n + 24) // 25
@cache
def dp(a: int, b: int) -> float:
if a <= 0 and b <= 0:
return 0.5
if a <= 0:
return 1.0
if b <= 0:
return 0.0
return 0.25 * (
dp(a - 4, b)
+ dp(a - 3, b - 1)
+ dp(a - 2, b - 2)
+ dp(a - 1, b - 3)
)
return dp(units, units)
Code Explanation
The large input cutoff avoids unnecessary computation:
if n >= 4800:
return 1.0
Then we convert milliliters into 25 ml units:
units = (n + 24) // 25
The + 24 implements ceiling division.
The memoized function stores results for repeated states:
@cache
def dp(a: int, b: int) -> float:
The base cases encode the scoring rule:
if a <= 0 and b <= 0:
return 0.5
if a <= 0:
return 1.0
if b <= 0:
return 0.0
The recursive case averages the four equally likely operations:
return 0.25 * (
dp(a - 4, b)
+ dp(a - 3, b - 1)
+ dp(a - 2, b - 2)
+ dp(a - 1, b - 3)
)
Finally, we start from equal soup amounts:
return dp(units, units)
Testing
def close(a, b, eps=1e-5):
return abs(a - b) <= eps
def run_tests():
s = Solution()
assert close(s.soupServings(50), 0.625)
assert close(s.soupServings(100), 0.71875)
assert close(s.soupServings(1), 0.625)
assert close(s.soupServings(25), 0.625)
assert close(s.soupServings(4800), 1.0)
print("all tests passed")
run_tests()
| Test | Why |
|---|---|
n = 50 |
Official small example |
n = 100 |
Official second example |
n = 1 |
Rounds up to one 25 ml unit |
n = 25 |
Same one-unit behavior |
n = 4800 |
Checks large-input cutoff |