## Tuesday, February 16, 2016

### SPOJ BTCODE_H (Maths) Solution - Java

Test Case given-

N = 2, K = 2.

# of words containing only 0 and 1 that are of length 2 -> 4

00
01
10
11

Now insertion of words may happen as:

00 00
00 01           01 00
00 10           10 00
00 11           11 00

01 01
01 10           10 01
01 11           11 01

10 10
10 11           11 10

11 11

Total # cases -> 16.

# cases where trie has 3 nodes = 4
4 nodes = 4
5 nodes = 8

Expected value of the number of nodes ->

(3*4 + 4*4 + 5*8)                                    68
----------------------         =             ---------------------             =              4.25
16                                                16

Source (Java):

```import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class BTCODE_HSimple {

//Exponentiation by Repeated Sqauring
public static double power(double a, int b){
if(b==0)return 1;
if(b==1)return a;
if(b%2==1){
return a*power(a*a, (b-1)/2);
}else return power(a*a, b/2);
}

public static void main(String[] args){
int n = IO.nextInt();
while(n-->0){
int N = IO.nextInt();
int K = IO.nextInt();
double ans = 1;
for(int i=1;i<=K;++i){
double p = power(0.5, i);
ans += 1;
double op = 1-p;
for(int j=1;j<N;++j){
ans += power(op, j);
}
}
System.out.printf("%.2f\n", ans);
}
}

/**************************************IO**************************************/

private static class IO {
private static InputStream stream = System.in;
private static byte[] buf = new byte[1024];
private static int curChar, numChars;

if (numChars == -1)throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)return -1;
}
return buf[curChar++];
}

public static int nextInt() {
while (isSpaceChar(c))
int sgn = 1;
if (c == '-') {
sgn = -1;
}
int res = 0;
do {
if (c < '0' || c > '9') throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

public static char nextChar() {
return (char) c;
}

private static String nextString(){
StringBuilder sb = new StringBuilder();
do{
sb.append((char)c);
return sb.toString();
}

private static boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

private static void println(Object... a){
for(Object o:a)System.out.print(o);
System.out.println();
}
}
}```