Toss Strange Coins

Easy
0/40
Average time to solve is 15m
profile
Contributed by
63 upvotes
Asked in company
Adobe

Problem statement

You are given ‘N’ coins, and an array ‘PROB’. These coins are “strange” because the probability of getting the head or tail is not ‘1/2’, the probability of getting a head face is denoted by the ‘PROB’ array. You are also given a positive integer ‘TARGET’, denoting the number of the coins facing heads you want if you toss every coin exactly once. Your task is to find out the “probability” of doing so.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains two positive integers, ‘N’, and ‘TARGET’, denoting the total number of coins and the number of coins facing heads respectively.

The second line of each test case contains ‘N’ space-separated real numbers, ‘PROB[i]’, representing the probability of the i-th coin of facing head when tossed.
Output Format : 
For each test case, print the “probability” that the head-facing coins equal ‘TARGET’, as described in the problem statement.

Output for each test case will be printed in a separate line.
Note : 
1. You do not need to print anything. It has already been taken care of. Just implement the given function.
2. Your answer will be accepted as correct if they are within 10^-6 of the correct answer.
Constraints : 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 1000
0 <= ‘TARGET’ <= N
0 <= ‘PROB[i]’ <= 1
PROB.length == ‘N’

Where ‘PROB[i]’  is the ith coin’s probability of facing the head when tossed.

Time Limit: 1sec
Sample Input 1 :
1
3 0 
0.5 0.2 0.3
Sample Output 1 :
0.280000
Explanation For Sample Input 1 :
The Probability of the 1st coin not getting a head = 1 - 0.5 = 0.5.
The Probability of the 2nd coin not getting a head = 1 - 0.2 = 0.8.
The Probability of the 3rd coin not getting a head = 1 - 0.3 = 0.7.
The Probability that ‘0’ coin shows the head = 0.5 * 0.8 * 0.7 = 0.28.
Sample Input 2 :
1
2 2
0.44 0.51
Sample Output 2 :
0.224400
Explanation For Sample Input 2 :
The probability that both coins shows the head = 0.44 * 0.51 = 0.2244.
Hint

Try to find all possible subsets of size TARGET.

Approaches (3)
Brute Force
  • 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.
Time Complexity

O(2^N), where ‘N’ is the number of coins.

 

We are using the recursion for forming all possible subsets. As in each function call, we have two options available, therefore, the time complexity will be O(2^N).

Space Complexity

O(1).

 

As we are only using the constant space.

Code Solution
(100% EXP penalty)
Toss Strange Coins
Full screen
Console