Ways to form Max Heap

Max Heap is a special kind of complete binary tree in which for every node the value present in that node is greater than the value present in it’s children nodes. If you want to know more about Heaps, please visit this link

So now the problem statement for this question is:

How many distinct Max Heap can be made from n distinct integers

In short, you have to ensure the following properties for the max heap :

Let us take an example of 4 distinct integers. Without loss of generality let us take 1 2 3 4 as our 4 distinct integers

Following are the possible max heaps from these 4 numbers :

         4 
       /  \ 
      3   2 
     / 
    1

4 / \ 2 3 / 1
4 / \ 3 1 / 2
These are the only possible 3 distinct max heaps possible for 4 distinct elements.

Implement the below function to return the number of distinct Max Heaps that is possible from n distinct elements.

As the final answer can be very large output your answer modulo 1000000007

Input Constraints : n <= 100

Method:


 L + R = (n-1) 
 (n-1)CL * getNumberOfMaxHeaps(L) * getNumberOfMaxHeaps(R) 
 L = 2h - 1 if p >= m/2
                   
= 2h - 1 - (m/2 - p) if p<(m/2)
Solution:

Time: O(n^2)
Space: O(n^2)

public class Solution {
    public int solve(int A) {
        long[][] combs = getCombs(A);
        return (int) (helper(A, combs) % 1000000007);
    }
    
    private long helper(int A, long[][] combs) {
        if (A <= 1) {
            return 1;
        }
        int n = A;
        int h = 0;
        while (A > 1) {
            h ++;
            A /= 2;
        }
        int m = (int) Math.pow(2, h);
        int p = n - (m - 1);
        // L = 2h - 1 if p >= m/2
        //   = 2h - 1 - (m/2 - p) if p<(m/2)
        int L = 0;
        if (p >= m / 2) {
            L = m - 1;
        } else {
            L = m - 1 - (m / 2 - p);
        }
        // System.out.println("m: " + m + " p: " + p + " L: " + L);
        return (((combs[n - 1][L] * helper(L, combs)) % 1000000007 * helper(n - 1 - L, combs) % 1000000007));
    }
    
    private long[][] getCombs(int A) {
        long[][] combs = new long[A + 1][A + 1];
        for (int n = 1; n <= A; n ++) {
            for (int r = 0; r <= n; r ++) {
                if (n == r || r == 0) {
                    combs[n][r] = 1;
                } else {
                    combs[n][r] = (combs[n - 1][r] + combs[n - 1][r - 1]) % 1000000007;
                }
            }
        }
        return combs;
    }
}