# Soup Servings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/soup-servings)
Canonical: https://scaleengineer.com/dsa/problems/soup-servings
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Probability and Statistics](https://scaleengineer.com/dsa/patterns/probability-and-statistics)
---
## Problem
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`

# Approaches
## Brute-force Recursion
This is the most straightforward approach, directly modeling the problem's recursive structure. A function calculates the probability for a given amount of soups A and B by recursively calling itself for the four possible operations and averaging the results. This approach does not store intermediate results, leading to severe performance issues.
**Time:** O(4^(n/25)), as each state branches into four, and the recursion depth is proportional to `n`. This exponential complexity makes the approach impractical for all but the smallest values of `n`. · **Space:** O(n/25), for the recursion call stack depth. The depth of the recursion is proportional to the initial amount of soup.
**Pros:** Simple to conceive and implement directly from the problem statement.
**Cons:** Extremely inefficient due to redundant computations of the same subproblems.; Results in a 'Time Limit Exceeded' (TLE) error for most inputs on competitive programming platforms.
### Explanation
The state of the problem is defined by the remaining amounts of soup A and B, `(a, b)`. We create a recursive function, `solve(a, b)`, to compute the desired probability. The function's logic is as follows:\n\n*   **Base Cases**: If `a <= 0` and `b <= 0`, both are empty, return 0.5. If only `a <= 0`, A is empty first, return 1.0. If only `b <= 0`, B is empty first, return 0.0.\n*   **Recursive Step**: For any other state `(a, b)`, the probability is the average of the probabilities of the four subsequent states: `0.25 * (solve(a-100, b) + solve(a-75, b-25) + solve(a-50, b-50) + solve(a-25, b-75))`.\n\nThe initial call is `solve(n, n)`. This method is highly inefficient as it repeatedly solves the same subproblems, leading to an exponential number of computations.
### Algorithm
*   Define a recursive function `solve(a, b)` that takes the current amounts of soup A and B.\n*   Inside the function, implement the base cases:\n    *   If `a <= 0` and `b <= 0`, return 0.5.\n    *   If `a <= 0`, return 1.0.\n    *   If `b <= 0`, return 0.0.\n*   If none of the base cases are met, make four recursive calls corresponding to the four serving operations and return their average: `0.25 * (solve(a-100, b) + solve(a-75, b-25) + solve(a-50, b-50) + solve(a-25, b-75))`.\n*   The main function initiates the process by calling `solve(n, n)`.

## Top-Down Dynamic Programming (Memoization)
This approach optimizes the brute-force recursion by using memoization to store and reuse the results of subproblems. By avoiding re-computation, it drastically improves efficiency. It also incorporates two key optimizations: scaling the problem size and handling large `n` as a special case where the probability converges to 1.
**Time:** O(N^2), where `N = ceil(n/25)`. Since we cap `n` at around 4800, `N` is at most ~192. So the complexity is effectively constant, O(192^2), for any `n`. · **Space:** O(N^2), where `N = ceil(n/25)`. Due to the large `n` optimization, `N` is capped at a constant (around 192), making the space complexity effectively O(1).
**Pros:** Highly efficient and passes within typical time limits.; The logic closely follows the recursive structure of the problem, making it relatively intuitive to understand.
**Cons:** Requires extra space for the memoization table.; Recursive calls might lead to stack overflow for extremely deep recursion, though this is not an issue here due to the `n` cap optimization.
### Explanation
This method refines the recursive solution with several key ideas:\n\n*   **State Scaling**: The soup amounts served are always multiples of 25. We can scale down the problem by considering units of 25ml. Let `N = ceil(n / 25)`. The operations now consume (4,0), (3,1), (2,2), and (1,3) units of soup (A, B).\n*   **Memoization**: A 2D array, `memo[i][j]`, is used to store the result of `solve(i, j)`. Before computing, the function checks the `memo` table. If a result exists, it's returned immediately. Otherwise, the result is computed, stored, and then returned.\n*   **Large `n` Optimization**: For large values of `n`, the probability of soup A running out first approaches 1. We can determine a threshold (e.g., `n >= 4800`) where the result is within `10^-5` of 1.0. For `n` above this threshold, we can return 1.0 directly, avoiding computation for very large state spaces.\n```java
class Solution {
    private double[][] memo;

    public double soupServings(int n) {
        // For large n, the probability approaches 1.
        // A threshold of 4800 is found empirically to be sufficient
        // for the answer to be within 10^-5 of 1.
        if (n >= 4800) {
            return 1.0;
        }
        
        // Scale down n by 25.
        int N = (n + 24) / 25;
        
        memo = new double[N + 1][N + 1];
        return solve(N, N);
    }

    private double solve(int a, int b) {
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1.0;
        if (b <= 0) return 0.0;
        
        if (memo[a][b] > 0) {
            return memo[a][b];
        }
        
        double prob = 0.25 * (solve(a - 4, b) + 
                              solve(a - 3, b - 1) + 
                              solve(a - 2, b - 2) + 
                              solve(a - 1, b - 3));
        
        memo[a][b] = prob;
        return prob;
    }
}
```
### Algorithm
*   Handle the large `n` case as an optimization: if `n` is sufficiently large (e.g., `n >= 4800`), return 1.0 immediately.\n*   Scale the problem size `n` down to `N = ceil(n / 25)`.\n*   Initialize a memoization table `memo` of size `(N+1)x(N+1)` to store results of subproblems.\n*   Use a recursive helper function `solve(a, b)` that first checks the base cases, then checks the memo table for a pre-computed result.\n*   If the state `(a,b)` is not memoized, compute its value recursively, store it in the table, and then return it.

## Bottom-Up Dynamic Programming (Tabulation)
This is an iterative dynamic programming approach, also known as tabulation. It builds the solution from the smallest subproblems up to the desired one. It uses a 2D table to store results, similar to memoization, but fills it iteratively. This approach often offers a slight performance benefit by avoiding the overhead associated with recursion.
**Time:** O(N^2), where `N = ceil(n/25)`. Effectively O(1) because `N` is bounded by a constant due to the large `n` optimization. · **Space:** O(N^2) for the DP table. With the optimization for large `n`, this is effectively O(1) as `N` is bounded.
**Pros:** Often the fastest implementation in practice due to being iterative and avoiding recursion overhead.; Guaranteed not to have stack overflow issues, which can be a concern with deep recursion.
**Cons:** The order of iteration needs to be carefully chosen to ensure subproblems are solved before they are needed.; Can be less intuitive to formulate than the top-down recursive approach for some problems.
### Explanation
This approach systematically fills a DP table `dp[i][j]` which stores the probability for `i` units of soup A and `j` units of B.\n\n*   **Initialization**: The table of size `(N+1)x(N+1)` (where `N = ceil(n/25)`) is initialized with base cases: `dp[0][0] = 0.5`, `dp[0][j] = 1.0` for `j>0`, and `dp[i][0] = 0.0` for `i>0`.\n*   **Iteration**: We use nested loops to iterate from `i=1` to `N` and `j=1` to `N`. In each cell `dp[i][j]`, we calculate the value based on the four previous states according to the recurrence relation: `dp[i][j] = 0.25 * (dp[max(0,i-4)][j] + dp[max(0,i-3)][max(0,j-1)] + ...)` The `max(0, ...)` function is used to handle boundary conditions correctly, mapping out-of-bounds indices to the base cases at row/column 0.\n*   **Result**: The final answer is found at `dp[N][N]`. This approach also benefits from the large `n` optimization.\n```java
class Solution {
    public double soupServings(int n) {
        if (n >= 4800) {
            return 1.0;
        }
        int N = (n + 24) / 25;
        double[][] dp = new double[N + 1][N + 1];

        dp[0][0] = 0.5;
        for (int i = 1; i <= N; i++) {
            dp[0][i] = 1.0;
            dp[i][0] = 0.0;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                double term1 = dp[Math.max(0, i - 4)][j];
                double term2 = dp[Math.max(0, i - 3)][Math.max(0, j - 1)];
                double term3 = dp[Math.max(0, i - 2)][Math.max(0, j - 2)];
                double term4 = dp[Math.max(0, i - 1)][Math.max(0, j - 3)];
                dp[i][j] = 0.25 * (term1 + term2 + term3 + term4);
            }
        }

        return dp[N][N];
    }
}
```
### Algorithm
*   Apply the large `n` optimization: if `n >= 4800`, return 1.0.\n*   Scale `n` down to `N = ceil(n / 25)`.\n*   Create a 2D DP table `dp` of size `(N+1)x(N+1)`.\n*   Initialize the first row and column of the table with the base case values: `dp[0][0]=0.5`, `dp[0][j]=1.0`, `dp[i][0]=0.0`.\n*   Use nested loops to iterate from `i=1` to `N` and `j=1` to `N`, filling the rest of the table using the recurrence relation.\n*   Return the final answer stored in `dp[N][N]`.

# Solutions
### Java

```java
class Solution { private double [][] f = new double [ 200 ][ 200 ]; public double soupServings ( int n ) { return n > 4800 ? 1 : dfs (( n + 24 ) / 25 , ( n + 24 ) / 25 ); } private double dfs ( int i , int j ) { if ( i <= 0 && j <= 0 ) { return 0.5 ; } if ( i <= 0 ) { return 1.0 ; } if ( j <= 0 ) { return 0 ; } if ( f [ i ][ j ] > 0 ) { return f [ i ][ j ]; } double ans = 0.25 * ( dfs ( i - 4 , j ) + dfs ( i - 3 , j - 1 ) + dfs ( i - 2 , j - 2 ) + dfs ( i - 1 , j - 3 )); f [ i ][ j ] = ans ; return ans ; } }
```

### CPP

```cpp
class Solution { public: double soupServings ( int n ) { double f [ 200 ][ 200 ] = { 0.0 }; function < double ( int , int ) > dfs = [ & ]( int i , int j ) -> double { if ( i <= 0 && j <= 0 ) return 0.5 ; if ( i <= 0 ) return 1 ; if ( j <= 0 ) return 0 ; if ( f [ i ][ j ] > 0 ) return f [ i ][ j ]; double ans = 0.25 * ( dfs ( i - 4 , j ) + dfs ( i - 3 , j - 1 ) + dfs ( i - 2 , j - 2 ) + dfs ( i - 1 , j - 3 )); f [ i ][ j ] = ans ; return ans ; }; return n > 4800 ? 1 : dfs (( n + 24 ) / 25 , ( n + 24 ) / 25 ); } };
```

### Python

```python
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 )
```