Skip to main content
Talentd

Soup Servings - Solution & Explanation

MediumMathDynamic ProgrammingProbability and Statistics20 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

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:

  1. Serve 100 ml of soup A and 0 ml of soup B,
  2. Serve 75 ml of soup A and 25 ml of soup B,
  3. Serve 50 ml of soup A and 50 ml of soup B, and
  4. Serve 25 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 <= 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.

Approach 1: DP with Memoization

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n^2) due to memoization.
Space Complexity: O(n^2) for the memoization table.

Try this approach in the editor →

Approach 2: Iterative DP Solution

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.

Code

JavaScriptC++

JavaScript

C++

Complexity

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.

Try this approach in the editor →

Approach 3: 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.

We design a function dfs(i, j), which represents the probability result when there are i units of soup A and j units of soup B remaining.

When i leq 0 and j leq 0, it means both soups are finished, and we should return 0.5. When i leq 0, it means soup A is finished first, and we should return 1. When j leq 0, it means soup B is finished first, and we should return 0.

Next, for each operation, we have four choices:

  • Take 4 units from soup A and 0 units from soup B;
  • Take 3 units from soup A and 1 unit from soup B;
  • Take 2 units from soup A and 2 units from soup B;
  • Take 1 unit from soup A and 3 units from soup B.

Each choice has a probability of 0.25, so we can derive:

$ dfs(i, j) = 0.25 times (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3))

We use memoization to store the results of the function.

Additionally, we find that when n=4800, the result is 0.999994994426, and the required precision is 10^{-5}. As n increases, the result gets closer to 1. Therefore, when n \gt 4800, we can directly return 1.

The time complexity is O(C^2), and the space complexity is O(C^2). In this problem, C=200$.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
DP with Memoization

Time Complexity: O(n^2) due to memoization.
Space Complexity: O(n^2) for the memoization table.

Iterative DP Solution

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.

Memoization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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.

Video Solution

Soup Servings | INTUITIVE | Recursion | Memoization | GOOGLE | Leetcode-808 • codestorywithMIK • 14,866 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Soup Servings easy or hard?
Soup Servings is rated Medium on LeetCode. The difficulty comes from recognizing the probability model, reducing the state space by dividing by 25, and applying dynamic programming to compute the final probability efficiently.
Soup Servings Python/Java solution
Python and Java implementations typically use recursive DP with memoization. The function dp(a, b) computes probabilities for each state and caches results in a dictionary or 2D array. Both languages easily support the top‑down DP pattern used in this problem.
How to solve Soup Servings in O(n)?
A strict O(n) solution is not typical for this problem. Instead, the common optimization observes that when n becomes large (around 4800 ml or more), the probability approaches 1. Implementations return 1 directly for large n, which effectively avoids computing the DP table for large inputs.
What is the best approach for Soup Servings?
Dynamic programming with memoization is the most effective approach. Define a state dp(a, b) representing the probability when soups A and B have a and b units remaining. By scaling the input to 25 ml units and caching results, the algorithm runs in O(m^2) time with O(m^2) space.
Is Soup Servings asked at Google/Amazon/Meta?
Soup Servings appears in interview preparation sets for companies that emphasize probability and dynamic programming, including Google and other large tech firms. It tests the ability to model probabilistic transitions and optimize state space with DP.
What data structure is used in Soup Servings?
The solution primarily uses a 2D dynamic programming table or a memoization map. Each entry stores the probability for a specific pair of remaining soup amounts. The structure prevents recomputation of overlapping subproblems.
What is the time complexity of Soup Servings?
The optimized dynamic programming solution runs in O(m^2) time where m = ceil(n / 25). Because the serving sizes are multiples of 25 ml, scaling reduces the original input size significantly. Space complexity is also O(m^2) for storing DP states.

Ready to solve this problem?

Practice Soup Servings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer