Ways to form Max Heap, Java

Ways to form Max Heap

//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_111

import java.util.*;
import java.lang.*;

class Rextester
{

int [] height;
	long[][] nCrCache;
	long [] dp ;
	int MOD = 1000000007;

public int solve(int n) {
    		
    		height = new int[n+1];
    		nCrCache = new long[n+1][n+1];
        dp = new long[n+1];
         
         int cpower = 1, clog = -1;
         for (int i = 1; i <= n; i++) {
             if (cpower == i) {
                 clog++;
                 cpower *= 2;
             }
             height[i] = clog;
         }
         
    	    return (int)heapCount(n);
    }
    
    private int getLeft(int n){ 
       
       if (n == 1)
           return 0;
    
       int h = height[n];
    
       //max number of possible elements in the greatest height
       int numh = (1 << h); //(2 ^ h)
    
       // last level count of elements.
       int last = n - ((1 << h) - 1);
    
       // if more than half of the greatest data filled.
       if (last >= (numh / 2))
           return (1 << h) - 1; 
       else
           return (1 << h) - 1 - ((numh / 2) - last);
       
    }
    
    
    public long heapCount(int n) {
         
    	     if(n<=2)
           return 1;
           
         int left = getLeft(n);

dp[n] = ( (choose(n-1,left)*heapCount(left))%MOD * heapCount(n-1-left))%MOD;
          
         return dp[n];
    }
    
	private long choose(int n, int r) {

if (r > n)
			return 0;
		if (n <= 1)
			return 1;
		if (r == 0)
			return 1;

if (nCrCache[n][r] != 0)
			return nCrCache[n][r];
		long answer = choose(n - 1, r - 1) + choose(n - 1, r);
		answer %= MOD;
		nCrCache[n][r] = answer;
		//System.out.println(answer);
		return answer;
	}

public static void main(String [] args){
	   
 	   int n = 100;
 	   //258365767
 	   Rextester e = new Rextester();
 	   System.out.println(e.solve(n));
   }
    
}


run \| edit \| history \| help	0