Soup Servings

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:

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

Examples

Example 1

1
2
3
4
5
6


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

1
2


Input: n = 100
Output: 0.71875

Constraints

0 <= n <= 109

Solution

Method 1 – DP with Memoization (Recursive Probability)

Intuition

We can model the problem as a recursive process, where at each step we try all four serving options and sum the probabilities. Memoization avoids recomputation. For large n, the answer approaches 1.

Approach

Scale n down by 25 (since all servings are multiples of 25) to reduce state space.
Use a recursive function with memoization to compute the probability for each (a, b).
For large n (n > 5000), return 1.0 directly for efficiency.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    double soupServings(int n) {
        if (n > 5000) return 1.0;
        int N = (n + 24) / 25;
        vector<vector<double>> memo(N+1, vector<double>(N+1, -1));
        function<double(int,int)> dp = [&](int a, int b) -> double {
            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 res = 0.25 * (dp(a-4,b) + dp(a-3,b-1) + dp(a-2,b-2) + dp(a-1,b-3));
            return memo[a][b] = res;
        };
        return dp(N,N);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func soupServings(n int) float64 {
    if n > 5000 { return 1.0 }
    N := (n + 24) / 25
    memo := make([][]float64, N+1)
    for i := range memo { memo[i] = make([]float64, N+1); for j := range memo[i] { memo[i][j] = -1 } }
    var dp func(a, b int) float64
    dp = func(a, b int) float64 {
        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] }
        res := 0.25 * (dp(a-4, b) + dp(a-3, b-1) + dp(a-2, b-2) + dp(a-1, b-3))
        memo[a][b] = res
        return res
    }
    return dp(N, N)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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];
        for (double[] row : memo) Arrays.fill(row, -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] >= 0) return memo[a][b];
        double res = 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] = res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    fun soupServings(n: Int): Double {
        if (n > 5000) return 1.0
        val N = (n + 24) / 25
        val memo = Array(N+1) { DoubleArray(N+1) { -1.0 } }
        fun dp(a: Int, b: Int): Double {
            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]
            val res = 0.25 * (dp(a-4, b) + dp(a-3, b-1) + dp(a-2, b-2) + dp(a-1, b-3))
            memo[a][b] = res
            return res
        }
        return dp(N, N)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def soupServings(self, n: int) -> float:
        if n > 5000:
            return 1.0
        N = (n + 24) // 25
        memo = [[-1.0]*(N+1) for _ in range(N+1)]
        def dp(a: int, b: int) -> float:
            if a <= 0 and 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]
            res = 0.25 * (dp(a-4, b) + dp(a-3, b-1) + dp(a-2, b-2) + dp(a-1, b-3))
            memo[a][b] = res
            return res
        return dp(N, N)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


impl Solution {
    pub fn soup_servings(n: i32) -> f64 {
        if n > 5000 { return 1.0; }
        let N = (n + 24) / 25;
        let N = N as usize;
        let mut memo = vec![vec![-1.0; N+1]; N+1];
        fn dp(a: usize, b: usize, memo: &mut Vec<Vec<f64>>) -> f64 {
            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.0 { return memo[a][b]; }
            let mut res = 0.0;
            let ops = [(4,0),(3,1),(2,2),(1,3)];
            for &(da, db) in &ops {
                let na = if a > da { a-da } else { 0 };
                let nb = if b > db { b-db } else { 0 };
                res += 0.25 * dp(na, nb, memo);
            }
            memo[a][b] = res;
            res
        }
        dp(N, N, &mut memo)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    soupServings(n: number): number {
        if (n > 5000) return 1.0;
        const N = Math.ceil(n / 25);
        const memo: number[][] = Array.from({length: N+1}, () => Array(N+1).fill(-1));
        function dp(a: number, b: number): number {
            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];
            memo[a][b] = 0.25 * (dp(a-4, b) + dp(a-3, b-1) + dp(a-2, b-2) + dp(a-1, b-3));
            return memo[a][b];
        }
        return dp(N, N);
    }
}

Complexity

⏰ Time complexity: O(n^2) for n <= 5000 (after scaling), otherwise O(1) for large n.
🧺 Space complexity: O(n^2) for the memoization table.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – DP with Memoization (Recursive Probability)#

Intuition#

Approach#

Code#

Complexity#