CodeSprint 2 : Coin Tosses

[20 points]

You have an unbiased coin which you want to keep tossing until you get N consecutive heads. You've tossed the coin M times and surprisingly, all tosses resulted in heads. What is the expected number of additional tosses needed until you get N consecutive heads?
Input:The first line contains the number of cases T. Each of the next T lines contains two numbers N and M.
Output:Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places.
Sample Input:4
2 0
2 1
3 3
3 2
Sample Output:6.00
4.00
0.00
8.00
Sample Explanations:If N = 2 and M = 0, you need to keep tossing the coin until you get 2 consecutive heads. It is not hard to show that on average, 6 coin tosses are needed.
If N = 2 and M = 1, you need 2 consecutive heads and have already have 1. You need to toss once more no matter what. In that first toss, if you get heads, you are done. Otherwise, you need to start over, as the consecutive counter resets, and you need to keep tossing the coin until you get N=2 consecutive heads. The expected number of coin tosses is thus 1 + (0.5 * 0 + 0.5 * 6) = 4.0
If N = 3 and M = 3, you already have got 3 heads, so you do not need any more tosses.
Constraints:1 <= T <= 100
1 <= N <= 1000
0 <= M <= N

This problem is a Mathematical Expectation problem
Mathematically, for a discrete variable X with probability function P(X), the expected value E[X] is given by Σ x_iP(x_i) the summation runs over all the distinct values x_i that the variable can take.

eg. find number of coin flips for getting a single head.
Let Expected number of coin flips for getting a head is x

a. If the first flip is the head, then we are done. The probability of this event is 1/2 and the number of coin flips for this event is 1. 
b. If the first flip is the tails, then we have to start over.The probability of this event is 1/2 and the expected number of coins flips now onwards is x. But we have already wasted one flip, so the total number of flips is x+1.
 this gives ,

x = (1/2)(1) + (1/2) (1+x)
Solving, we get x = 2. 

similarly for n consecutive heads ,

a. if 1st , 2nd , 3rd or nth flip gives tail then we have to start all over again.

b. else we are done

a  & b gives , x = (1/2)(x+1) + (1/4)(x+2) + ... + (1/(2^k))(x+k) + .. + (1/(2^N))(x+N)  + (1/(2^N))(N)

 we get x = 2^N+1-2 .

 or 

let En be the probability for n consecutive heads  means

In order to obtain n consecutive heads, we must first obtain n − 1 consecutive heads, followed by:

• with probability ½, a further head; or
• with probability ½, a tail, after which we must obtain n consecutive heads.

It follows that E_n = ½(E_n−1 + 1) + ½(E_n−1 + 1 + E_n), from which E_n = 2E_n−1 + 2. which also give En = 2^N+1-2  .

 Now as per given problem we already have M number of heads therefore let rest number of coin flips required be x.

let k =N-M be the consecutive heads required.

so

a. if 1st , 2nd , 3rd or kth flip gives tail then we have to start all over again ie. to find n consecutive heads.
b. else we are done
which gives
y =  (1/2)(x+1) + (1/4)(x+2) + ... + (1/(2^k))(x+k)  + (1/(2^(N-k)))(k)
and x = 2^N+1-2.
solving this gives , 
y = 2^{N+1 -} 2^M+1


java code : 

import java.math.BigInteger;
    import java.util.Scanner;
    public class Solution {
          public static void main(String[] args) {
            Scanner a = new Scanner(System.in);
            int t= a.nextInt();
            while(t--!=0){
                int n=a.nextInt();
                int m = a.nextInt();
            BigInteger b = BigInteger.valueOf(2).pow(n+1);
           BigInteger c= BigInteger.valueOf(2).pow(m+1);
            System.out.println(b.subtract(c)+".00");
        }}
    }

Python one :

#!/usr/bin/python
t = int(raw_input())
while t :
    n, m = map(int, raw_input().split())
    k = 2**(n+1)-2**(m+1)
    print '.'.join(map(str,[k,"00"]))
    t = t-1