Soup Servings

MediumProbability DP · Memoisation🧩 Probability DP LeetCode #808 ↗Updated Oct 30, 2026

Problem

Two soups, A and B, each start with n ml. Each turn one of four servings is picked with probability 1/4: (A 100, B 0), (A 75, B 25), (A 50, B 50) or (A 25, B 75) ml. If a soup has less than requested, serve what is left. Stop as soon as either soup is empty. Return

P(A empties first) + ½ · P(both empty
        together)

Inputn = 50Output0.62500

Inputn = 100Output0.71875

0 ≤ n ≤ 10⁹ · answers within 10^-5 are accepted

Try it yourself

Java

class Solution {
    public double soupServings(int n) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Every serving is a multiple of 25, so work in units of 25 ml (m = ⌈n/25⌉). On average A loses 2.5 units and B 1.5 per turn, so A is heavily favoured: once n > 4800 the answer is within 10^-5 of 1 and we can return 1 directly.

PatternProbability DP

Instinct Asked for a probability or expected value after random moves? Run DP over (step, state) and split each state's mass across every outcome.

Memory hack Pour the probability like water - split it across the moves, let what spills off the board drain away, and the puddle that's left is your answer.

Open the Probability DP guide →

Approaches

Brute ForcePlain Recursion over All Serving Sequences

Time O(4^n/100)Space O(n/100)

f(a, b) returns 0.5 if both are empty, 1 if only A is empty, 0 if only B is empty, else the average of the four next states. Every turn removes 100 ml in total, so the depth is about 2n/100 and each level branches 4 ways.

Java

public double soupServings(int n) {
    return serve(n, n);
}

private double serve(int a, int b) {
    if (a <= 0 && b <= 0) return 0.5;
    if (a <= 0) return 1.0;
    if (b <= 0) return 0.0;
    return 0.25 * (serve(a - 100, b) + serve(a - 75, b - 25)
                 + serve(a - 50, b - 50) + serve(a - 25, b - 75));
}

Faithful to the rules but exponential — only works for a few hundred ml.

BetterMemoisation in 25 ml Units

Time O(m²)Space O(m²)

Divide by 25 (rounding up, since a partial serving still empties the soup) to get m units; servings become (4,0), (3,1), (2,2), (1,3). Only (m+1)² states (a, b) exist, so cache them.

Java

private double[][] memo;

public double soupServings(int n) {
    int m = (n + 24) / 25; // units of 25 ml, rounded up
    memo = new double[m + 1][m + 1];
    for (double[] row : memo) Arrays.fill(row, -1);
    return f(m, m);
}

private double f(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 p = 0.25 * (f(a - 4, b) + f(a - 3, b - 1) + f(a - 2, b - 2) + f(a - 1, b - 3));
    return memo[a][b] = p;
}

Exact and fast for small n, but n = 10⁹ needs a 4×10⁷-squared table.

OptimalMemoisation + Convergence Cut-off

Time O(1)Space O(1)

The answer increases towards 1 as n grows; at n = 4800 (192 units) it is already 0.999995. So for larger n return 1, and otherwise run the memo, whose table never exceeds 193×193 — a constant bound.

Java

private double[][] memo;

public double soupServings(int n) {
    if (n > 4800) return 1.0; // answer is within 1e-5 of 1 from here on
    int m = (n + 24) / 25;
    memo = new double[m + 1][m + 1];
    for (double[] row : memo) Arrays.fill(row, -1);
    return f(m, m);
}

private double f(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 p = 0.25 * (f(a - 4, b) + f(a - 3, b - 1) + f(a - 2, b - 2) + f(a - 1, b - 3));
    return memo[a][b] = p;
}

Handles n up to 10⁹ instantly; the cut-off is the whole trick.

Pro tip

You don't need to memorise 4800: say “A drains faster, so the value converges to 1 — I'd find the threshold by printing f(m) for growing m”.

At a glance

Level	Approach	Time	Space
Brute Force	Plain Recursion over All Serving Sequences	`O(4^n/100)`	`O(n/100)`
Better	Memoisation in 25 ml Units	`O(m²)`	`O(m²)`
Optimal	Memoisation + Convergence Cut-off	`O(1)`	`O(1)`

Common pitfalls

Using n / 25 instead of rounding up — 1 ml of soup still counts as a unit.
Returning 1 for “both empty” instead of 0.5.
Allocating an m×m table for n = 10⁹ without the cut-off (memory error).

Interview tips

Spot the gcd of all servings (25) early — it shrinks the state space 625×.
Explain the asymmetry: expected A per turn is 62.5 ml vs 37.5 ml for B.
Justify the cut-off with the 10^-5 tolerance stated in the problem.

Pattern

Probability DP + convergence → huge input range but a tolerance on the answer hints that the value saturates.

My notes saved in this browser