Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

808. Soup Servings - Leetcode Solution

Code Implementation

from functools import lru_cache

class Solution:
    def soupServings(self, n: int) -> float:
        if n > 5000:
            return 1.0

        @lru_cache(None)
        def dp(a, b):
            if a <= 0 and b <= 0:
                return 0.5
            if a <= 0:
                return 1.0
            if b <= 0:
                return 0.0
            return 0.25 * (
                dp(a-100, b) +
                dp(a-75, b-25) +
                dp(a-50, b-50) +
                dp(a-25, b-75)
            )
        return dp(n, n)
      
class Solution {
public:
    double soupServings(int N) {
        if (N > 5000) return 1.0;
        vector<vector<double>> memo(200, vector<double>(200, -1.0));
        function<double(int,int)> dp = [&](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.5) return memo[a][b];
            return memo[a][b] = 0.25 * (
                dp(a-4, b) +
                dp(a-3, b-1) +
                dp(a-2, b-2) +
                dp(a-1, b-3)
            );
        };
        int n = (N + 24) / 25;
        return dp(n, n);
    }
};
      
class Solution {
    public double soupServings(int N) {
        if (N > 5000) return 1.0;
        int n = (N + 24) / 25;
        Double[][] memo = new Double[n + 1][n + 1];
        return dp(n, n, memo);
    }

    private double dp(int a, int b, Double[][] memo) {
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1.0;
        if (b <= 0) return 0.0;
        if (memo[a][b] != null) return memo[a][b];
        memo[a][b] = 0.25 * (
            dp(a - 4, b, memo) +
            dp(a - 3, b - 1, memo) +
            dp(a - 2, b - 2, memo) +
            dp(a - 1, b - 3, memo)
        );
        return memo[a][b];
    }
}
      
var soupServings = function(N) {
    if (N > 5000) return 1.0;
    const memo = {};
    function dp(a, b) {
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1.0;
        if (b <= 0) return 0.0;
        let key = a + ',' + b;
        if (memo[key] !== undefined) return memo[key];
        memo[key] = 0.25 * (
            dp(a - 4, b) +
            dp(a - 3, b - 1) +
            dp(a - 2, b - 2) +
            dp(a - 1, b - 3)
        );
        return memo[key];
    }
    let n = Math.ceil(N / 25);
    return dp(n, n);
};

Problem Description

Imagine you have two types of soup, Soup A and Soup B, each starting with n milliliters. At each turn, you randomly choose one of four possible serving combinations (each with equal probability) to serve from the soups:
  • Serve 100 ml from A, 0 ml from B
  • Serve 75 ml from A, 25 ml from B
  • Serve 50 ml from A, 50 ml from B
  • Serve 25 ml from A, 75 ml from B
The process repeats until at least one soup runs out (goes to zero or below). The goal is to compute the probability that Soup A will run out first, plus half the probability that both run out at the same time. The answer should be accurate up to 10-6.
Key Constraints:
  • 0 <= n <= 10^9
  • Each serving choice is equally likely (probability 0.25)
  • Solve for large n efficiently

Thought Process

At first glance, you might consider simulating every possible sequence of servings, but the number of possibilities grows exponentially with n. This brute-force approach is clearly infeasible for large values of n.

The key insight is that the problem has overlapping subproblems and optimal substructure, making it suitable for dynamic programming (DP). We can model the state as the remaining amounts of Soup A and Soup B, and recursively compute the probability for each state, caching results to avoid redundant computation.

Additionally, since all serving sizes are multiples of 25 ml, we can scale down n by dividing by 25, greatly reducing the state space. For very large n, the probability approaches 1, so we can use an early cutoff for efficiency.

Solution Approach

To solve this problem efficiently, we use memoized recursion (top-down dynamic programming) with the following steps:
  1. Normalize the units: Since all serving sizes are multiples of 25, we divide n by 25 and round up. This reduces the problem size.
  2. Define the state: Each state is represented by the remaining units of Soup A and Soup B.
  3. Base cases:
    • If both soups run out at the same time, return 0.5.
    • If only A runs out, return 1.0.
    • If only B runs out, return 0.0.
  4. Recursive case: For each state, compute the expected probability by considering all four serving options, each with probability 0.25. Use memoization to cache results for each state.
  5. Optimization for large n: If n is large (e.g., above 5000), the answer is very close to 1.0, so we can return 1.0 directly for efficiency.
Justification:
  • Memoization (caching) is critical to avoid recomputing probabilities for the same state.
  • Scaling down by 25 reduces the number of unique states and makes the DP feasible.
  • The cutoff for large n is based on the problem's probabilistic behavior and required precision.

Example Walkthrough

Sample Input: n = 50
Step 1: Normalize units: n = ceil(50 / 25) = 2. So both Soup A and B start with 2 units.
Step 2: Compute dp(2, 2):
  • Option 1: Serve (4,0): dp(-2,2) → A is empty, B is not. Probability = 1.0
  • Option 2: Serve (3,1): dp(-1,1) → A is empty, B is not. Probability = 1.0
  • Option 3: Serve (2,2): dp(0,0) → Both empty. Probability = 0.5
  • Option 4: Serve (1,3): dp(1,-1) → B is empty, A is not. Probability = 0.0
Step 3: Weighted sum:
ans = 0.25 * (1.0 + 1.0 + 0.5 + 0.0) = 0.25 * 2.5 = 0.625
So, the answer for n = 50 is 0.625.

Time and Space Complexity

Brute-force:
  • Time: Exponential, as each serving can branch into four possibilities, leading to O(4n/25) states.
  • Space: Proportional to the recursion stack, also exponential.
Optimized DP:
  • Time: O((n/25)2), since we memoize each unique (a, b) state and there are about (n/25)2 possible pairs.
  • Space: O((n/25)2) for the memoization table.
  • For large n (n > 5000), we shortcut and return 1.0 directly, making the solution very efficient.

Summary

The Soup Servings problem is a great example of using dynamic programming and memoization to efficiently solve a probabilistic process with overlapping subproblems. By normalizing the serving sizes, defining a clear DP state, and caching results, we avoid the combinatorial explosion of brute-force recursion. The early cutoff for large n leverages the problem's probabilistic behavior to deliver fast, accurate results. The solution is elegant because it combines mathematical insight with algorithmic optimization for both correctness and efficiency.