Soup Servings - Video Solutions
Soup Servings | INTUITIVE | Recursion | Memoization | GOOGLE | Leetcode-808
Soup Servings - Video Solution
Watch 10 video solutions for Soup Servings, a medium level problem involving Math, Dynamic Programming, Probability and Statistics. This walkthrough by codestorywithMIK has 14,866 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- Serve
100ml of soup A and0ml of soup B, - Serve
75ml of soup A and25ml of soup B, - Serve
50ml of soup A and50ml of soup B, and - Serve
25ml of soup A and75ml 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 <= 109
Approach Overview
Problem 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.
Complexity Analysis
| 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. |