#808

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Soup Servings

Compute the probability that soup A empties before soup B using state transition dynamic programming efficiently.

math dynamic programming probability and statistics

Problem Statement

You have two soups, A and B, each starting with n milliliters. On each turn, one of four serving operations is randomly selected with equal probability. Each operation reduces the amounts of A and B by fixed quantities. The goal is to determine the probability that soup A will become empty before soup B, with ties counting as half probability.

The process stops immediately once either soup reaches zero. Because the quantities decrease in discrete steps and operations are random, naive simulation is inefficient for large n. You must use state transition dynamic programming to efficiently track all possible states and their probabilities, handling overlaps and memoization carefully.

Examples

Example 1

Input: n = 50

Output: 0.62500

If we perform either of the first two serving operations, soup A will become empty first. If we perform the third operation, A and B will become empty at the same time. If we perform the fourth operation, B will become empty first. So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.

Example 2

Input: n = 100

Output: 0.71875

If we perform the first serving operation, soup A will become empty first. If we perform the second serving operations, A will become empty on performing operation [1, 2, 3], and both A and B become empty on performing operation 4. If we perform the third operation, A will become empty on performing operation [1, 2], and both A and B become empty on performing operation 3. If we perform the fourth operation, A will become empty on performing operation 1, and both A and B become empty on performing operation 2. So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.71875.

Constraints

0 <= n <= 109

Solution Approach

Model as discrete state transitions

Define DP states as dp[a][b], representing the probability that soup A empties first when A has a mL and B has b mL. Each serving operation leads to a new state with adjusted soup quantities, updating the probability as the sum of all outcomes multiplied by 0.25.

Apply memoization or iterative DP

Use recursion with memoization to avoid recomputing overlapping subproblems, or implement a bottom-up iterative DP table. Store intermediate probabilities for all states until both soups are exhausted or one reaches zero, ensuring accurate accumulation of probabilities for large n.

Optimize for large n using threshold approximation

For very large n, the probability approaches 1. Use a cutoff where further recursion yields negligible probability change. This approximation maintains O(1) practical complexity while preserving correctness within an acceptable error margin.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(1)

The DP approach effectively treats the problem as bounded by the number of discrete 25 mL units, allowing O(1) time and space in practical execution using approximation and memoization, despite the theoretical unbounded n.

What Interviewers Usually Probe

Watch for floating-point accumulation errors in probability sums.
Notice if the candidate considers naive simulation versus DP state modeling.
Check understanding of stopping conditions and tie probabilities.

Common Pitfalls or Variants

Common pitfalls

Ignoring half probability when both soups empty simultaneously.
Failing to memoize overlapping DP states leading to exponential recursion.
Incorrectly handling state transitions when soup quantities drop below zero.

Follow-up variants

Change serving sizes or probabilities to test flexible DP modeling.
Ask for probability that soup B empties first instead of A.
Introduce more soups or more complex serving patterns to extend state space.

FAQ

What is the main idea behind solving Soup Servings?

Use state transition dynamic programming to model the probability that soup A empties before B, caching intermediate results to optimize recursion.

How do I handle large n values efficiently?

Approximate probabilities when n is large by using thresholds where further recursion contributes negligibly, ensuring practical O(1) performance.

Why is memoization necessary in this problem?

Without memoization, the recursion recomputes many overlapping states, leading to exponential runtime and potential stack overflow.

How are ties between soups handled?

If both soups become empty simultaneously, count it as half the probability for soup A emptying first, following the problem definition.

Can I use iterative DP instead of recursion for Soup Servings?

Yes, iterative DP builds the probability table bottom-up and avoids recursion depth issues while still applying the state transition logic.

terminal

Solution

Solution 1: Memoization Search

In this problem, since each operation is a multiple of $25$, we can consider every $25ml$ of soup as one unit. This reduces the data scale to $\left \lceil \frac{n}{25} \right \rceil$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def soupServings(self, n: int) -> float:
        @cache
        def dfs(i: int, j: int) -> float:
            if i <= 0 and j <= 0:
                return 0.5
            if i <= 0:
                return 1
            if j <= 0:
                return 0
            return 0.25 * (
                dfs(i - 4, j)
                + dfs(i - 3, j - 1)
                + dfs(i - 2, j - 2)
                + dfs(i - 1, j - 3)
            )

        return 1 if n > 4800 else dfs((n + 24) // 25, (n + 24) // 25)

Continue Practicing

#837 new 21 game #1227 airplane seat assignment probability #1467 probability of a two boxes having the same number of distinct balls