_1230. Toss Strange Coins.md

1230. Toss Strange Coins

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 29, 2024

Last updated : July 29, 2024

---

Related Topics : Array, Math, Dynamic Programming, Probability and Statistics

Acceptance Rate : 58.09 %

---

Solutions

• m1230 v1 Memoization.py
• m1230 v2 Iterative Matrix DP.py
• m1230 v2.c
• m1230 v2.java

Python

m1230 v1 Memoization.py

class Solution:
    def probabilityOfHeads(self, prob: List[float], target: int) -> float:
        discludeRest = prob.copy()
        discludeRest[-1] = 1 - discludeRest[-1]
        for i in range(len(prob) - 2, -1, -1) :
            discludeRest[i] = discludeRest[i + 1] * (1 - prob[i])

        @cache
        def recurs(indx: int, remaining: int) -> bool :
            if indx >= len(prob) :
                if remaining :
                    return 0
                return 1

            if not remaining :
                return discludeRest[indx]

            return recurs(indx + 1, remaining - 1) * prob[indx] + \
                    recurs(indx + 1, remaining) * (1 - prob[indx])

        return recurs(0, target)

m1230 v2 Iterative Matrix DP.py

class Solution:
    def probabilityOfHeads(self, prob: List[float], target: int) -> float:
        sols = [[0] * (target + 1) for _ in range(len(prob) + 1)]
        sols[0][0] = 1

        for r in range(1, len(prob) + 1) :
            sols[r][0] = sols[r - 1][0] * (1 - prob[r - 1])
            for c in range(1, target + 1) :
                sols[r][c] = sols[r - 1][c] * (1 - prob[r - 1]) + \
                             sols[r - 1][c - 1] * prob[r - 1]

        return sols[-1][-1]

C

m1230 v2.c

double probabilityOfHeads(double* prob, int probSize, int target){
    double sols[probSize + 1][target + 1];
    for (int r = 0; r < probSize + 1; r++) {
        memset(sols[r], 0, sizeof(double) * (target + 1));
    }
    sols[0][0] = 1;

    for (int r = 1; r < probSize + 1; r++) {
        sols[r][0] = sols[r - 1][0] * (1 - prob[r - 1]);
        for (int c = 1; c < target + 1; c++) {
            sols[r][c] = sols[r - 1][c] * (1 - prob[r - 1])
                            + sols[r - 1][c - 1] * prob[r - 1];
        }
    }

    return sols[probSize][target];
}

Java

m1230 v2.java

class Solution {
    public double probabilityOfHeads(double[] prob, int target) {
        double[][] sols = new double[prob.length + 1][target + 1];
        sols[0][0] = 1;

        for (int r = 1; r < prob.length + 1; r++) {
            sols[r][0] = sols[r - 1][0] * (1 - prob[r - 1]);
            for (int c = 1; c < target + 1; c++) {
                sols[r][c] = sols[r - 1][c] * (1 - prob[r - 1])
                                + sols[r - 1][c - 1] * prob[r - 1];
            }
        }

        return sols[sols.length - 1][sols[0].length - 1];
    }
}