Toss Strange Coins

• The idea here is to find all possible subsets of size equal to TARGET. We can use the recursion for this.
• For every ith element, we have two options:
  • Include the ith element in the subset.
  • Not include the ith element in the subset.
• If we are including the ith element, then we have to multiply the answer by the PROB[i]. Otherwise, multiply the answer by the (1 - PROB[i]).
• If we have processed all the elements, then we have to check the following conditions:
  • If the size of the subset equals the TARGET, return 1.
  • If the size of the subset is not equal to the TARGET, return 0.
• At each function call we require the following states:
  • index: current index i of the array PROB.
  • currentSize: the size of the current subset.
  • prob: the array ‘PROB’
  • target: the given ‘TARGET’ value.

• If you look closely at ‘approach 1’, there are repeated subproblems. How to handle these kinds of problems? Yes, you are right!. We have to use Dynamic Programming.
• We can store the result of each function call in some new array, and if we encounter a repeated subproblem, then simply return the previously saved result. This technique is known as memoization.

Algorithm

• Create a 2D array named memo of the datatype double, to store the result of the function calls, i.e., double memo[N+1][N+1], and ‘N’ can go up to ‘1000’, so our memo will become memo[1001][1001]. Here, memo[i][j] implies that we are at index ‘i’ and the subset’s current size is ‘j’.
• Initialize it with -1.
• Call the function solve(index, currentSize, prob, target), where the index is the current index of the array, currentSize is the current subset size, prob is the probability array ‘PROB’, and the target is the given ‘TARGET’ value.
• Return the return value of the above function.

double solve(int index, int currentSize, double prob[], int target):

• If index == prob.size:
  • If currentSize == target, return 1.
  • Else, return 0.
• If we have already solved the current function call, i.e., if memo[index][currentSize] != -1, then return the stored value.
• Now, we have two options available:
  • Include the current element in the subset, call solve(index+1, currentSize+1, prob, target) * prob[index].
  • Not include the current element, call solve(index+1, currentSize+1, prob, target) * (1 - prob[index]).
• Return dp[index][currentSize] = summation of above two result.

• The idea here is to use bottom-up dynamic programming.
• This approach can also be solved by using the 2-states dp same as approach ‘2’ but here, we are using only 1-state dp.
• Create an array of datatype ‘double’ of size ‘TARGET+1’ named dp, where dp[i] denotes the probability that the ‘i’ coins facing heads. Fill dp with ‘0’.
• Initialize dp[0] = 1.0.
• Run a loop from i = 0 to i < |PROB|, in each iteration do:
  • Now, we run a backward loop from the j = min(TARGET, i + 1) to ‘0’, in each iteration:
    • If j == 0 (which means that the ‘i’th coin have to face ‘tail’), then dp[j] = dp[j] * (1 - PROB[i]).
    • Else, we have to add two things in the current dp state:
      • Keep ‘i’th coin as tail, dp[j] = dp[j] * (1 - PROB[i]).
      • Keep ‘i’th coin as head, dp[j] = dp[j] + (dp[j-1] * PROB[i]).
• Return dp[TARGET].