There are two types of soup: type A and type B. Initially, we have n ml of each type of soup. There are four kinds of operations:
100 ml of soup A and 0 ml of soup B,75 ml of soup A and 25 ml of soup B,50 ml of soup A and 50 ml of soup B, and25 ml of soup A and 75 ml of soup B.When we serve some soup, we give it to someone, and we no longer have it. Each turn, we will choose from the four operations with an equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as possible. We stop once we no longer have some quantity of both types of soup.
Note that we do not have an operation where all 100 ml's of soup B are used first.
Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: n = 50 Output: 0.62500 Explanation: If we choose the first two operations, A will become empty first. For the third operation, A and B will become empty at the same time. For 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
Constraints:
0 <= n <= 109Problem Overview: Two soups A and B start with n ml each. Four serving operations remove different amounts from A and B with equal probability. The task is to compute the probability that soup A becomes empty first plus half the probability that both become empty at the same time.
Approach 1: DP with Memoization (Top‑Down) (Time: O(m^2), Space: O(m^2))
The key observation is that every operation removes multiples of 25 ml. You can scale the problem by converting n into units of 25 using m = ceil(n / 25). This dramatically reduces the state space. Define a recursive function dp(a, b) representing the probability when A has a units and B has b. For each state, recursively evaluate the four serving options and average their probabilities. Base cases handle when A or B becomes empty. Memoize results in a hash map or 2D array to avoid recomputing overlapping states, a classic pattern in dynamic programming. A further optimization: when n becomes large (around 4800 ml), the probability approaches 1, so you can return 1 directly.
Approach 2: Iterative DP (Bottom‑Up) (Time: O(m^2), Space: O(m^2))
The same state definition dp[a][b] can be computed iteratively instead of recursion. Build a 2D table where each cell stores the probability for that soup state. Initialize base cases for when A or B is empty, then iterate over increasing values of a and b. Each state averages the probabilities of the four transitions corresponding to the serving operations. This avoids recursion overhead and guarantees deterministic iteration order. The approach combines ideas from math (probability modeling) and probability and statistics to compute the expected outcome.
Recommended for interviews: The DP with memoization approach is what interviewers usually expect. It demonstrates that you recognize overlapping subproblems and reduce the state space by scaling with 25 ml units. Mentioning the large‑n optimization (return 1 when n is big) shows strong analytical thinking and awareness of probability convergence.
We can use a dynamic programming approach with memoization to store the probability results for known quantities of soup A and B. We'll treat the problem states as a grid where each cell holds the probability of that state leading to soup A becoming empty first. The key to optimizing this solution is to memoize intermediate results to avoid redundant calculations by storing probabilities in a 2D array or dictionary.
In this Python solution, we use a recursive function with memoization. If the amount of soup A or B is less than or equal to zero, we return the base probabilities. The recursive step calculates the probability for each serving option and stores the result in a memo dictionary to avoid recalculating. For large n, greater than 4800, the probability approaches 1, so we return 1 directly.
Time Complexity: O(n^2) due to memoization.
Space Complexity: O(n^2) for the memoization table.
An alternative is solving the problem iteratively using a DP table to store results for each state. We build up from small values to larger values of soup A and B, filling out the DP table based on possible outcomes until we reach the desired amounts.
We use a 2D array dp to compute probabilities iteratively. Each cell in the DP table is filled based on the results of possible soup servings. The getDP helper function handles edge cases like negative indices to ensure correctness.
JavaScript
C++
Time Complexity: O(n^2) as we fill up each cell of an N-by-N table.
Space Complexity: O(n^2) for maintaining the DP table.
| Approach | Complexity |
|---|---|
| DP with Memoization | Time Complexity: O(n^2) due to memoization. |
| Iterative DP Solution | Time Complexity: O(n^2) as we fill up each cell of an N-by-N table. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DP with Memoization (Top‑Down) | O(m^2) | O(m^2) | Best general solution. Easy to express recursively with memoization for overlapping states. |
| Iterative DP (Bottom‑Up) | O(m^2) | O(m^2) | Preferred when avoiding recursion or when implementing DP tables explicitly. |
Soup Servings | INTUITIVE | Recursion | Memoization | GOOGLE | Leetcode-808 • codestorywithMIK • 14,207 views views
Watch 9 more video solutions →Practice Soup Servings with our built-in code editor and test cases.
Practice on FleetCode