CareerCup

package interview_questions;

/**
*
* @author just_do_it
*
*/
public class CountBinaryHeaps {


/*
* f(38) = 37C22 * f(15) * f(22)
*/
static long numBinaryHeaps(int n){
if(n == 1 || n == 2) {
return 1;
} else if (n == 3){
return 2;
}

int numElementsChild1, numElementsChild2;
int n1 = largestPowerOf2LessOrEqual(n);
if(n1 - 1 + n1/2 >= n){
numElementsChild1 = n1/2 - 1;
numElementsChild2 = n - n1/2;
} else {
numElementsChild1 = n1 -1;
numElementsChild2 = n - n1;
}

long res = choose(n-1,numElementsChild1) * numBinaryHeaps(numElementsChild1) * numBinaryHeaps(numElementsChild2);
return res;
}

public static int choose(int n, int m){
if(n < m)
return 0;
if(m == 0 || n == m)
return 1;
return choose(n-1,m-1)+choose(n-1,m);
}

static int largestPowerOf2LessOrEqual(int n){
int pow2 = 1;

while(pow2*2 < n){
pow2 *= 2;
}
return pow2;
}

public static void main(String[] args){

int[] testcases = {1 , 2 , 3 , 4 , 5 , 6};
long[] results = {1 , 1 , 2 , 3 , 4*2, 10*2 };
for(int i = 0; i < testcases.length; i++){
int n = testcases[i];
long res = numBinaryHeaps(n);
System.out.println(n + "\t" + res + "\t" + results[i]);
}
}
}

package interview_questions;

/**
 * 
 * @author just_do_it
 *
 */
public class CountBinaryHeaps {

	
	/*
	 * f(38) = 37C22 * f(15) * f(22)
	 */
	static long numBinaryHeaps(int n){
		if(n == 1 || n == 2) {
			return 1;
		} else if (n == 3){
			return 2;
		}
		
		int numElementsChild1, numElementsChild2;
		int n1 = largestPowerOf2LessOrEqual(n);
		if(n1 - 1 + n1/2 >= n){
			numElementsChild1 = n1/2 - 1;
			numElementsChild2 = n - n1/2;
		} else {
			numElementsChild1 = n1 -1;
			numElementsChild2 = n - n1;
		}
		
		long res = choose(n-1,numElementsChild1) * numBinaryHeaps(numElementsChild1) * numBinaryHeaps(numElementsChild2);
		return res;
	}
	
	public static int choose(int n, int m){
	    if(n < m)
	        return 0;
	    if(m == 0 || n == m)
	        return 1;
	    return choose(n-1,m-1)+choose(n-1,m);
	}
	
	static int largestPowerOf2LessOrEqual(int n){
		int pow2 = 1;
		
		while(pow2*2 < n){
			pow2 *= 2;
		}
		return pow2;
	}
	
	public static void main(String[] args){
		   
		   int[] testcases = {1 , 2 , 3 , 4 , 5 ,  6};
		   long[] results = {1 , 1 , 2 , 3 , 4*2, 10*2  };
		   for(int i = 0; i < testcases.length; i++){
			   int n = testcases[i];
			   long res = numBinaryHeaps(n);
			   System.out.println(n + "\t" + res + "\t" + results[i]);
		   }
	   }
}

i think it is catalan number and is (n+1)*( 2n choose n)