LeetCode 808: Soup Servings

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:

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

Examples

Example 1:

n = 50

Each soup starts with 50 ml.

The four possible first operations give:

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:

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:

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)

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()